Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Mika Göös:

TR22-003 | 4th January 2022
Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere

On Semi-Algebraic Proofs and Algorithms

We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-$d$ Sherali-Adams refutation of an unsatisfiable CNF formula $C$ if and only if there is an $\varepsilon > 0$ and a degree-$d$ conical junta $J$ such that $viol_C(x) - \varepsilon = J$, where $viol_C(x)$ counts ... more >>>

TR21-012 | 9th February 2021
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

On the Power and Limitations of Branch and Cut

Revisions: 1

The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas -- certain unsatisfiable systems of linear equations mod 2 -- which are canonical ... more >>>

ISSN 1433-8092 | Imprint