All reports by Author Yaroslav Alekseev:

__
TR24-072
| 11th April 2024
__

Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch#### Tropical proof systems

__
TR24-037
| 26th February 2024
__

Yaroslav Alekseev, Yuval Filmus, Alexander Smal#### Lifting dichotomies

Revisions: 1

__
TR22-176
| 1st December 2022
__

Yaroslav Alekseev, Edward Hirsch#### The power of the Binary Value Principle

__
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

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

Yaroslav Alekseev, Yuval Filmus, Alexander Smal

Lifting theorems are used for transferring lower bounds between Boolean function complexity measures. Given a lower bound on a complexity measure $A$ for some function $f$, we compose $f$ with a carefully chosen gadget function $g$ and get essentially the same lower bound on a complexity measure $B$ for the ... more >>>

Yaroslav Alekseev, Edward Hirsch

The (extended) Binary Value Principle (eBVP, the equation $\sum x_i 2^{i-1} = -k$ for $k > 0$

and in the presence of $x_i^2=x_i$) has received a lot of attention recently, several lower

bounds have been proved for it [Alekseev et al 20, Alekseev 21, Part and Tzameret 21].

Also ...
more >>>

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