Blackbox Polynomial Identity Testing for Depth 3 Circuits

DOI10.1109/FOCS.2009.67zbMath1292.68095MaRDI QIDQ5171176

Neeraj Kayal, Shubhangi Saraf

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Related Items (18)

Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Deterministic identity testing for sum of read-once oblivious arithmetic branching programs ⋮ Unnamed Item ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ Interactions of computational complexity theory and mathematics ⋮ Sylvester-Gallai type theorems for quadratic polynomials ⋮ Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in ⋮ Read-once polynomial identity testing ⋮ Recent Results on Polynomial Identity Testing ⋮ Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin. ⋮ Depth-4 Identity Testing and Noether’s Normalization Lemma ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ A generalized sylvester-gallai type theorem for quadratic polynomials ⋮ Unnamed Item ⋮ Improved hitting set for orbit of ROABPs ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits ⋮ IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM

This page was built for publication: Blackbox Polynomial Identity Testing for Depth 3 Circuits