Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits

DOI10.1137/05063605XzbMath1124.68042MaRDI QIDQ5422493

Zeev Dvir, Amir Shpilka

Publication date: 22 October 2007

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

Full work available at URL: https://doi.org/10.1137/05063605x

zbMATH Keywords

Derandomization; arithmetic circuits; locally decodable codes; depth 3; polynomial identity test

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

94B65: Bounds on codes

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Sylvester-Gallai type theorems for quadratic polynomials, A generalized sylvester-gallai type theorem for quadratic polynomials, Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits, Depth-4 Identity Testing and Noether’s Normalization Lemma, Subexponential size hitting sets for bounded depth multilinear formulas, A novel elementary construction of matching vectors, Read-once polynomial identity testing, Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin., Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in, Towards lower bounds on locally testable codes via density arguments, Building above read-once polynomials: identity testing and hardness of representation, Deterministic polynomial identity tests for multilinear bounded-read formulae, Deterministically testing sparse polynomial identities of unbounded degree, Deterministic identity testing for sum of read-once oblivious arithmetic branching programs, Improved hitting set for orbit of ROABPs, Lossless dimension expanders via linearized polynomials and subspace designs, IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM, Recent Results on Polynomial Identity Testing