Multi-linear formulas for permanent and determinant are of super-polynomial size
DOI10.1145/1502793.1502797zbMATH Open1325.68112OpenAlexW2023541349MaRDI QIDQ5899508FDOQ5899508
Authors: Ran Raz 
Publication date: 11 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1502793.1502797
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Determinants, permanents, traces, other special matrix functions (15A15)
Cited In (38)
- Multi-\(k\)-ic depth three circuit lower bound
- Characterizing propositional proofs as noncommutative formulas
- Title not available (Why is that?)
- A super-quadratic lower bound for depth four arithmetic circuits
- On the Symmetries of and Equivalence Test for Design Polynomials.
- Title not available (Why is that?)
- Resource trade-offs in syntactically multilinear arithmetic circuits
- A Selection of Lower Bounds for Arithmetic Circuits
- On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
- Limitations of sums of bounded read formulas and ABPs
- Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
- Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
- Title not available (Why is that?)
- 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
- Approaching the chasm at depth four
- An exponential lower bound for homogeneous depth four arithmetic formulas
- 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?
- Title not available (Why is that?)
- Title not available (Why is that?)
- On proving parameterized size lower bounds for multilinear algebraic models
- Lower bounds for special cases of syntactic multilinear ABPs
- Lower bounds for depth-4 formulas computing iterated matrix multiplication
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)
