Multi-linear formulas for permanent and determinant are of super-polynomial size
From MaRDI portal
Publication:5901079
DOI10.1145/1007352.1007353zbMath1192.68328WikidataQ56578981 ScholiaQ56578981MaRDI QIDQ5901079
Publication date: 15 August 2010
Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1007352.1007353
15A15: Determinants, permanents, traces, other special matrix functions
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Non-commutative circuits and the sum-of-squares problem, Lower bounds for monotone \(q\)-multilinear Boolean circuits, Optimal sparse matrix dense vector multiplication in the I/O-model, Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors, Homogeneous formulas and symmetric polynomials, Resolution over linear equations and multilinear proofs, On \(\epsilon\)-sensitive monotone computations, Algebraic Complexity Classes, Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials, Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity, Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
