Multi-linear formulas for permanent and determinant are of super-polynomial size
From MaRDI portal
Publication:5899508
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
(38)- Multi-k-ic depth three circuit lower bound
- Characterizing propositional proofs as noncommutative formulas
- scientific article; zbMATH DE number 7204375 (Why is no real title available?)
- Resource trade-offs in syntactically multilinear arithmetic circuits
- A super-quadratic lower bound for depth four arithmetic circuits
- On the Symmetries of and Equivalence Test for Design Polynomials.
- scientific article; zbMATH DE number 7561696 (Why is no real title available?)
- A Selection of Lower Bounds for Arithmetic Circuits
- Limitations of sums of bounded read formulas and ABPs
- On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
- Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
- Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
- scientific article; zbMATH DE number 7250151 (Why is no real title available?)
- Subexponential size hitting sets for bounded depth multilinear formulas
- On the hardness of the determinant: sum of regular set-multilinear circuits
- The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- Unifying known lower bounds via geometric complexity theory
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- A note on parameterized polynomial identity testing using hitting set generators
- Non-commutative computations: lower bounds and polynomial identity testing
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Barriers for rank methods in arithmetic complexity
- Lower bounds for the sum of small-size algebraic branching programs
- Lower bounds for the determinantal complexity of explicit low degree polynomials
- Notes on Boolean read-\(k\) and multilinear circuits
- An exponential lower bound for homogeneous depth four arithmetic formulas
- Approaching the chasm at depth four
- Algebraic proofs over noncommutative formulas
- Read-once polynomial identity testing
- Sums of read-once formulas: how many summands are necessary?
- On the complexity of the permanent in various computational models
- Sums of read-once formulas: how many summands suffice?
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- On proving parameterized size lower bounds for multilinear algebraic models
- Lower bounds for depth-4 formulas computing iterated matrix multiplication
- Lower bounds for special cases of syntactic multilinear ABPs
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)
