Search Results

Motivated by practical applications in the design of optimization compilers for neural networks, we initiated the study of identity testing problems for arithmetic circuits augmented with exponentiation gates that compute the real function x↦ e^x. These circuits compute real functions of form P(→x)/P'(→x), where both P(→x) and P'(→x) are exponential polynomials ∑_{i = 1}^k f_i(→x)⋅ exp((g_i(→x))/(h_i(→x))), for polynomials f_i(→x),g_i(→x), and h_i(→x). We formalize a black-box query model over finite fields for this class of circuits, which is mathematical simple and reflects constraints faced by real-world neural network compilers. We proved that a simple and efficient randomized identity testing algorithm achieves perfect completeness and non-trivial soundness. Concurrent with our work, the algorithm has been implemented in the optimization compiler Mirage by Wu et al. (OSDI 2025), demonstrating promising empirical performance in both efficiency and soundness error. Finally, we propose a number-theoretic conjecture under which our algorithm is sound with high probability.

In a recent work, Fan, Li, and Yang (STOC 2022) constructed a family of almost-universal hash functions such that each function in the family is computable by (2n + o(n))-gate circuits of fan-in 2 over the B₂ basis. Applying this family, they established the existence of pseudorandom functions computable by circuits of the same complexity, under the standard assumption that OWFs exist. However, a major disadvantage of the hash family construction by Fan, Li, and Yang (STOC 2022) is that it requires a seed length of poly(n), which limits its potential applications. We address this issue by giving an improved construction of almost-universal hash functions with seed length polylog(n), such that each function in the family is computable with POLYLOGTIME-uniform (2n + o(n))-gate circuits. Our new construction has the following applications in both complexity theory and cryptography. - (Hardness magnification). Let α : ℕ → ℕ be any function such that α(n) ≤ log n / log log n. We show that if there is an n^{α(n)}-sparse NP language that does not have probabilistic circuits of 2n + O(n/log log n) gates, then we have (1) NTIME[2ⁿ] ⊈ SIZE[2^{n^{1/5}}] and (2) NP ⊈ SIZE[n^k] for every constant k. Complementing this magnification phenomenon, we present an O(n)-sparse language in P which requires probabilistic circuits of size at least 2n - 2. This is the first result in hardness magnification showing that even a sub-linear additive improvement on known circuit size lower bounds would imply NEXP ⊄ P_{/poly}. Following Chen, Jin, and Williams (STOC 2020), we also establish a sharp threshold for explicit obstructions: we give an explict obstruction against (2n-2)-size circuits, and prove that a sub-linear additive improvement on the circuit size would imply (1) DTIME[2ⁿ] ⊈ SIZE[2^{n^{1/5}}] and (2) P ⊈ SIZE[n^k] for every constant k. - (Extremely efficient construction of pseudorandom functions). Assuming that one of integer factoring, decisional Diffie-Hellman, or ring learning-with-errors is sub-exponentially hard, we show the existence of pseudorandom functions computable by POLYLOGTIME-uniform AC⁰[2] circuits with 2n + o(n) wires, with key length polylog(n). We also show that PRFs computable by POLYLOGTIME-uniform B₂ circuits of 2n + o(n) gates follows from the existence of sub-exponentially secure one-way functions.