2026-07-22T08:35:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14285 2024-03-06T10:53:52Z ddc:004 open_access

Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits Dutta, Pranjal Dwivedi, Prateek Saxena, Nitin Polynomial identity testing hitting set depth-4 circuits Polynomial Identity Testing (PIT) is a fundamental computational problem. The famous depth-4 reduction (Agrawal & Vinay, FOCS'08) has made PIT for depth-4 circuits, an enticing pursuit. The largely open special-cases of sum-product-of-sum-of-univariates (Σ^[k] Π Σ ∧) and sum-product-of-constant-degree-polynomials (Σ^[k] Π Σ Π^[δ]), for constants k, δ, have been a source of many great ideas in the last two decades. For eg. depth-3 ideas (Dvir & Shpilka, STOC'05; Kayal & Saxena, CCC'06; Saxena & Seshadhri, FOCS'10, STOC'11); depth-4 ideas (Beecken, Mittmann & Saxena, ICALP'11; Saha,Saxena & Saptharishi, Comput.Compl.'13; Forbes, FOCS'15; Kumar & Saraf, CCC'16); geometric Sylvester-Gallai ideas (Kayal & Saraf, FOCS'09; Shpilka, STOC'19; Peleg & Shpilka, CCC'20, STOC'21). We solve two of the basic underlying open problems in this work. We give the first polynomial-time PIT for Σ^[k] Π Σ ∧. Further, we give the first quasipolynomial time blackbox PIT for both Σ^[k] Π Σ ∧ and Σ^[k] Π Σ Π^[δ]. No subexponential time algorithm was known prior to this work (even if k = δ = 3). A key technical ingredient in all the three algorithms is how the logarithmic derivative, and its power-series, modify the top Π-gate to ∧. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pranjal Dutta and Prateek Dwivedi and Nitin Saxena 2021 Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2021.11 urn:nbn:de:0030-drops-142857 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.11 eng https://creativecommons.org/licenses/by/4.0/legalcode