License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2021.11
URN: urn:nbn:de:0030-drops-142857
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14285/
Go to the corresponding LIPIcs Volume Portal

Dutta, Pranjal ; Dwivedi, Prateek ; Saxena, Nitin

Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits

pdf-format:
LIPIcs-CCC-2021-11.pdf (1 MB)

Abstract

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 ∧.

BibTeX - Entry

@InProceedings{dutta_et_al:LIPIcs.CCC.2021.11,
  author =	{Dutta, Pranjal and Dwivedi, Prateek and Saxena, Nitin},
  title =	{{Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{11:1--11:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14285},
  URN =		{urn:nbn:de:0030-drops-142857},
  doi =		{10.4230/LIPIcs.CCC.2021.11},
  annote =	{Keywords: Polynomial identity testing, hitting set, depth-4 circuits}
}

Keywords: Polynomial identity testing, hitting set, depth-4 circuits
Collection: 36th Computational Complexity Conference (CCC 2021)
Issue Date: 2021
Date of publication: 08.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI