Multi-linear formulas for permanent and determinant are of super-polynomial size
From MaRDI portal
(Redirected from Publication:5899508)
Multi-linear formulas for permanent and determinant are of super-polynomial size (scientific article; zbMATH DE number 6507186)
Multi-linear formulas for permanent and determinant are of super-polynomial size (scientific article; zbMATH DE number 6507186)
Recommendations
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Separation of multilinear circuit and formula size
- Lower bounds and separations for constant depth multilinear circuits
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
- Improved construction for universality of determinant and permanent
Cited in
(43)- Sums of read-once formulas: how many summands are necessary?
- Multi-k-ic depth three circuit lower bound
- On the complexity of the permanent in various computational models
- Limitations of sums of bounded read formulas and ABPs
- On the hardness of the determinant: sum of regular set-multilinear circuits
- Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
- A note on parameterized polynomial identity testing using hitting set generators
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- Unifying known lower bounds via geometric complexity theory
- A Selection of Lower Bounds for Arithmetic Circuits
- The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
- Lower bounds for depth-4 formulas computing iterated matrix multiplication
- An exponential lower bound for homogeneous depth four arithmetic formulas
- Subexponential size hitting sets for bounded depth multilinear formulas
- Resource trade-offs in syntactically multilinear arithmetic circuits
- Characterizing propositional proofs as noncommutative formulas
- On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Read-once polynomial identity testing
- On proving parameterized size lower bounds for multilinear algebraic models
- Barriers for rank methods in arithmetic complexity
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
- Lower bounds for multilinear order-restricted ABPs
- On the Symmetries of and Equivalence Test for Design Polynomials.
- A super-quadratic lower bound for depth four arithmetic circuits
- scientific article; zbMATH DE number 7204375 (Why is no real title available?)
- scientific article; zbMATH DE number 7250151 (Why is no real title available?)
- Non-commutative computations: lower bounds and polynomial identity testing
- Approaching the chasm at depth four
- Sums of read-once formulas: how many summands suffice?
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Lower bounds for special cases of syntactic multilinear ABPs
- Lower bounds for the determinantal complexity of explicit low degree polynomials
- Algebraic proofs over noncommutative formulas
- Lower bounds for the sum of small-size algebraic branching programs
- Notes on Boolean read-k and multilinear circuits
- Superpolynomial lower bounds against low-depth algebraic circuits
- Improved lower bound, and proof barrier, for constant depth algebraic circuits
- Lower bounds for the sum of small-size algebraic branching programs
- Asymptotic spectra: theory, applications, and extensions
- New bounds for the ideal proof system in positive characteristic
This page was built for publication: Multi-linear formulas for permanent and determinant are of super-polynomial size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5899508)
