Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?

DOI10.1145/3357713.3384245MaRDI QIDQ5144897zbMATH OpenOpenAlexWikidataFDO

Authors Yaroslav Alekseev, Edward A. Hirsch, Iddo Tzameret, Dima Grigoriev

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

algebraic complexityalgebraic proofsproof complexitysemi-algebraic proofssum-of-squares proofstau-conjecture

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• scientific article; zbMATH DE number 7471587
• Proof complexity lower bounds from algebraic circuit complexity
• Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system
• (Semi)Algebraic proofs over {±1} variables
• scientific article; zbMATH DE number 2086627

Cited in

(7)

• The power of the binary value principle
• Propositional proof complexity
• On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Bounds on the total coefficient size of nullstellensatz proofs of the pigeonhole principle
• Algebraic proof systems (invited talk)
• New bounds for the ideal proof system in positive characteristic

This page was built for publication: Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144897)