Blackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn't matter

DOI10.1137/10848232zbMATH Open1272.68162arXiv1011.3234OpenAlexW2015393485MaRDI QIDQ4907583FDOQ4907583

Authors: Nitin Saxena, C. Seshadhri 

Publication date: 4 February 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: Let C be a depth-3 circuit with n variables, degree d and top fanin k (called sps(k,d,n) circuits) over base field F. It is a major open problem to design a deterministic polynomial time blackbox algorithm that tests if C is identically zero. Klivans & Spielman (STOC 2001) observed that the problem is open even when k is a constant. This case has been subjected to a serious study over the past few years, starting from the work of Dvir & Shpilka (STOC 2005). We give the first polynomial time blackbox algorithm for this problem. Our algorithm runs in time poly(nd^k), regardless of the base field. The only field for which polynomial time algorithms were previously known is F=Q (Kayal & Saraf, FOCS 2009, and Saxena & Seshadhri, FOCS 2010). This is the first blackbox algorithm for depth-3 circuits that does not use the rank based approaches of Karnin & Shpilka (CCC 2008). We prove an important tool for the study of depth-3 identities. We design a blackbox polynomial time transformation that reduces the number of variables in a sps(k,d,n) circuit to k variables, but preserves the identity structure.

Full work available at URL: https://arxiv.org/abs/1011.3234

Recommendations

• Blackbox identity testing for bounded top fanin depth-3 circuits, the field doesn't matter
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Polynomial identity testing for depth 3 circuits
• Black-box identity testing of depth-4 multilinear circuits
• From sylvester-gallai configurations to rank bounds

zbMATH Keywords

polynomial identity testingdepth-3 circuitblackbox algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Cited In (19)

• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Title not available (Why is that?)
• Recent results on polynomial identity testing
• Variety evasive subspace families
• An almost optimal rank bound for depth-3 identities
• Algebraic independence and blackbox identity testing
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Deterministic identity testing of depth-\(4\) multilinear circuits with bounded top fan-in
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• A generalized sylvester-gallai type theorem for quadratic polynomials
• From sylvester-gallai configurations to rank bounds
• Read-once polynomial identity testing
• Linear independence, alternants, and applications
• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
• Title not available (Why is that?)
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• Improved hitting set for orbit of ROABPs
• Depth-4 identity testing and Noether's normalization lemma
• Sylvester-Gallai type theorems for quadratic polynomials

This page was built for publication: Blackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn't matter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4907583)