Multi-linear formulas for permanent and determinant are of super-polynomial size
From MaRDI portal
Publication:5899508
DOI10.1145/1502793.1502797zbMath1325.68112MaRDI QIDQ5899508
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
68Q25: Analysis of algorithms and problem complexity
15A15: Determinants, permanents, traces, other special matrix functions
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, Characterizing Propositional Proofs as Noncommutative Formulas, On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models, Unnamed Item, Barriers for Rank Methods in Arithmetic Complexity, Towards Optimal Depth Reductions for Syntactically Multilinear Circuits, On the Symmetries of and Equivalence Test for Design Polynomials., A super-quadratic lower bound for depth four arithmetic circuits, Approaching the Chasm at Depth Four, Sums of Read-Once Formulas: How Many Summands Suffice?, Lower bounds for special cases of syntactic multilinear ABPs, Subexponential size hitting sets for bounded depth multilinear formulas, Resource trade-offs in syntactically multilinear arithmetic circuits, Read-once polynomial identity testing, Lower bounds for the determinantal complexity of explicit low degree polynomials, Algebraic proofs over noncommutative formulas, 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
