The Surprising Power of Constant Depth Algebraic Proofs

DOI10.1145/3373718.3394754zbMath1498.03151OpenAlexW3028950990MaRDI QIDQ5145666

Toniann Pitassi, Russell Impagliazzo, Sasank Mouli

Publication date: 21 January 2021

Published in: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3373718.3394754

zbMATH Keywords

polynomial calculusproof complexitybounded depthalgebraic proofs\(\mathrm{AC}^0[\mathrm{p}\)-Frege]

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (1)

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

This page was built for publication: The Surprising Power of Constant Depth Algebraic Proofs