3 papers
cs.CC2022
The power of the Binary Value Principle
Yaroslav Alekseev, Edward A. Hirsch
The (extended) Binary Value Principle (eBVP: for and ) has received a lot of attention recently, several lower bounds have been prov…
cs.CC2020
A Lower Bound for Polynomial Calculus with Extension Rule
Yaroslav Alekseev
In this paper we study an extension of the Polynomial Calculus proof system where we can introduce new variables and take a square root. We prove that an instance of the subset-sum…
cs.CC2019
Semi-Algebraic Proofs, IPS Lower Bounds and the -Conjecture: Can a Natural Number be Negative?
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch +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…