Multi-linear formulas for permanent and determinant are of super-polynomial size

DOI10.1145/1007352.1007353zbMath1192.68328OpenAlexW2046919433WikidataQ56578981 ScholiaQ56578981MaRDI QIDQ5901079

Ran Raz

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

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Optimal sparse matrix dense vector multiplication in the I/O-model ⋮ Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors ⋮ Lower bounds for monotone \(q\)-multilinear Boolean circuits ⋮ On \(\epsilon\)-sensitive monotone computations ⋮ Homogeneous formulas and symmetric polynomials ⋮ Resolution over linear equations and multilinear proofs ⋮ Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae ⋮ Non-commutative circuits and the sum-of-squares problem ⋮ 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

This page was built for publication: Multi-linear formulas for permanent and determinant are of super-polynomial size