Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
From MaRDI portal
Publication:5422493
DOI10.1137/05063605XzbMath1124.68042OpenAlexW1991584875MaRDI QIDQ5422493
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
Related Items (23)
Subexponential size hitting sets for bounded depth multilinear formulas ⋮ 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 ⋮ A novel elementary construction of matching vectors ⋮ 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 ⋮ Lossless dimension expanders via linearized polynomials and subspace designs ⋮ Recent Results on Polynomial Identity Testing ⋮ Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin. ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Depth-4 Identity Testing and Noether’s Normalization Lemma ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ Linear independence, alternants, and applications ⋮ Building above read-once polynomials: identity testing and hardness of representation ⋮ Unnamed Item ⋮ 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: Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
