2026-07-24T08:44:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25382 2026-03-19T13:04:18Z ddc:004 open_access

Identity Testing for Circuits with Exponentiation Gates Li, Jiatu Wu, Mengdi Polynomial Identity Testing Exponential Polynomials 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jiatu Li and Mengdi Wu 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.95 urn:nbn:de:0030-drops-253821 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.95 eng https://creativecommons.org/licenses/by/4.0/legalcode