Subexponential size hitting sets for bounded depth multilinear formulas

DOI10.1007/S00037-016-0131-1zbMATH Open1344.68090OpenAlexW1883887292MaRDI QIDQ301528FDOQ301528

Amir Shpilka, Rafael Oliveira, Ben Lee Volk

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/

Recommendations

• scientific article; zbMATH DE number 6829282
• Quasi-polynomial hitting-set for set-depth-\({\Delta}\) formulas
• A quadratic size-hierarchy theorem for small-depth multilinear formulas
• Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree
• Tensor-rank and lower bounds for arithmetic formulas

zbMATH Keywords

arithmetic circuitsderandomizationpolynomial identity testing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• A probabilistic remark on algebraic program testing
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• PRIMES is in P
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• On identity testing of tensors, low-rank recovery and compressed sensing
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic circuits: the chasm at depth four gets wider
• On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors
• Lower bounds on arithmetic circuits via partial derivatives
• 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
• Title not available (Why is that?)
• 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
• Improved Polynomial Identity Testing for Read-Once Formulas
• Title not available (Why is that?)
• Title not available (Why is that?)
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• A super-polynomial lower bound for regular arithmetic formulas
• Title not available (Why is that?)
• Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in
• 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
• 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

Cited In (5)

• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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

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