All reports by Author Dima Grigoriev:

__
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

Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch, Iddo Tzameret

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 >>>