Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SEMI-ALGEBRAIC PROOFS:
Reports tagged with semi-algebraic proofs:
TR19-142 | 23rd October 2019
Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch, Iddo Tzameret

Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?

Revisions: 1

We introduce the `binary value principle' which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems in proof and algebraic complexity. We prove conditional superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of this instance, ... more >>>


TR24-072 | 11th April 2024
Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch

Tropical proof systems

Revisions: 1

Propositional proof complexity deals with the lengths of polynomial-time verifiable proofs for Boolean tautologies. An abundance of proof systems is known, including algebraic and semialgebraic systems, which work with polynomial equations and inequalities, respectively. The most basic algebraic proof system is based on Hilbert's Nullstellensatz (Beame et al., 1996). Tropical ... more >>>




ISSN 1433-8092 | Imprint