Circuit Complexity, Proof Complexity, and Polynomial Identity Testing

DOI10.1145/3230742zbMath1426.68097arXiv1404.3820OpenAlexW2903251947WikidataQ128861616 ScholiaQ128861616MaRDI QIDQ4625658

Joshua A. Grochow, Toniann Pitassi

Publication date: 25 February 2019

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1404.3820

zbMATH Keywords

syzygiesdeterminantlower boundspermanentpolynomial calculuspolynomial identity testingVNP\(\mathrm{AC}^0[p\)-Frege]

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (7)

Hardness Characterisations and Size-width Lower Bounds for QBF Resolution ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ The power of the binary value principle ⋮ On vanishing sums of roots of unity in polynomial calculus and sum-of-squares ⋮ Unnamed Item ⋮ Witnessing matrix identities and proof complexity ⋮ Resolution with counting: dag-like lower bounds and different moduli

This page was built for publication: Circuit Complexity, Proof Complexity, and Polynomial Identity Testing