We study the performance of the Sherali-Adams system for VERTEX COVER on graphs with vector
chromatic number $2+\epsilon$. We are able to construct solutions for LPs derived by any number of Sherali-Adams tightenings by introducing a new tool to establish Local-Global Discrepancy. When restricted to
$O(1/ \epsilon)$ tightenings we show ... more >>>

We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n^Omega(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n^O(w) is essentially tight. ... more >>>

The propositional proof system Sherali-Adams (SA) has polynomial-size proofs of the pigeonhole principle (PHP). Similarly, the Nullstellensatz (NS) proof system has polynomial size proofs of the bijective (i.e. both functional and onto) pigeonhole principle (ofPHP). We characterize the strength of these algebraic proof systems in terms of Boolean proof systems ... more >>>

Recently it was shown that PLS is not contained in PPADS (ECCC report TR22-058). We show that this separation already implies that PLS is not contained in PPP. These separations are shown for the decision tree model of TFNP and imply similar separations in the type-2, relativized model.

Important note. ... more >>>

The complexity class PPP contains all total search problems many-one reducible to the PIGEON problem, where we are given a succinct encoding of a function mapping n+1 pigeons to n holes, and must output two pigeons that collide in a hole. PPP is one of the “original five” syntactically-defined subclasses ... more >>>