Subexponential size hitting sets for bounded depth multilinear formulas
From MaRDI portal
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
Cites work
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 6829282 (Why is no real title available?)
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- A probabilistic remark on algebraic program testing
- A super-polynomial lower bound for regular arithmetic formulas
- Arithmetic circuits: a chasm at depth 3
- Arithmetic circuits: a survey of recent results and open questions
- Arithmetic circuits: the chasm at depth four gets wider
- Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
- Black-box identity testing of depth-4 multilinear circuits
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
- Blackbox identity testing for bounded top fanin depth-3 circuits
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
- Deterministic polynomial identity testing in non-commutative models
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Fast Parallel Computation of Polynomials Using Few Processors
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Hardness-randomness tradeoffs for bounded depth arithmetic circuits
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Improved Bounds for Reduction to Depth 4 and Depth 3
- Improved Polynomial Identity Testing for Read-Once Formulas
- Jacobian hits circuits: hitting-sets, lower bounds for depth-\(D\) occur-\(k\) formulas \& depth-\(3\) transcendence degree-\(k\) circuits
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- Lower bounds and separations for constant depth multilinear circuits
- Lower bounds on arithmetic circuits via partial derivatives
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- On identity testing of tensors, low-rank recovery and compressed sensing
- On the relation between polynomial identity testing and finding variable disjoint factors
- PRIMES is in P
- Polynomial identity testing for depth 3 circuits
- Quasi-polynomial hitting-set for set-depth-\({\Delta}\) formulas
- Read-once polynomial identity testing
- Separation of multilinear circuit and formula size
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
Cited in
(7)- A quadratic size-hierarchy theorem for small-depth multilinear formulas
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- scientific article; zbMATH DE number 6829282 (Why is no real title available?)
- Quasi-polynomial hitting-set for set-depth-\({\Delta}\) formulas
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)
