Subexponential size hitting sets for bounded depth multilinear formulas

DOI10.1007/s00037-016-0131-1zbMath1344.68090OpenAlexW1883887292MaRDI QIDQ301528

F. Blanchet-Sadri, M. Dambrine

Publication date: 30 June 2016

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5054/

zbMATH Keywords

derandomizationarithmetic circuitspolynomial identity testing

Mathematics Subject Classification ID

Related Items (2)

Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Arithmetic circuits: the chasm at depth four gets wider
• Lower bounds and separations for constant depth multilinear circuits
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• A probabilistic remark on algebraic program testing
• Lower bounds on arithmetic circuits via partial derivatives
• PRIMES is in P
• Deterministic polynomial identity testing in non-commutative models
• Polynomial identity testing for depth 3 circuits
• Arithmetic Circuits: A Chasm at Depth 3
• Improved Bounds for Reduction to Depth 4 and Depth 3
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic Circuits: A survey of recent results and open questions
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
• On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors
• Improved Polynomial Identity Testing for Read-Once Formulas
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• A super-polynomial lower bound for regular arithmetic formulas
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in
• On identity testing of tensors, low-rank recovery and compressed sensing
• Jacobian hits circuits
• Black-box identity testing of depth-4 multilinear circuits
• Blackbox identity testing for bounded top fanin depth-3 circuits
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• Quasi-polynomial hitting-set for set-depth-Δ formulas
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: Subexponential size hitting sets for bounded depth multilinear formulas