All reports by Author Noah Fleming:

__
TR22-141
| 20th October 2022
__

Sam Buss, Noah Fleming, Russell Impagliazzo#### TFNP Characterizations of Proof Systems and Monotone Circuits

Revisions: 2

__
TR22-051
| 18th April 2022
__

Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida#### Low Degree Testing over the Reals

__
TR22-003
| 4th January 2022
__

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere#### On Semi-Algebraic Proofs and Algorithms

Revisions: 1

__
TR21-158
| 12th November 2021
__

Noah Fleming, Toniann Pitassi, Robert Robere#### Extremely Deep Proofs

Revisions: 1

__
TR21-061
| 29th April 2021
__

Noah Fleming, Toniann Pitassi#### Reflections on Proof Complexity and Counting Principles

__
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: 2

__
TR19-106
| 12th August 2019
__

Noah Fleming, Pravesh Kothari, Toniann Pitassi#### Semialgebraic Proofs and Efficient Algorithm Design

Revisions: 5

__
TR17-151
| 8th October 2017
__

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere#### Stabbing Planes

Revisions: 3

__
TR17-045
| 7th March 2017
__

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere#### Random CNFs are Hard for Cutting Planes

Revisions: 2

Sam Buss, Noah Fleming, Russell Impagliazzo

Connections between proof complexity and circuit complexity have become major tools for obtaining lower bounds in both areas. These connections -- which take the form of interpolation theorems and query-to-communication lifting theorems -- translate efficient proofs into small circuits, and vice versa, allowing tools from one area to be applied ... more >>>

Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida

We study the problem of testing whether a function $f: \mathbb{R}^n \to \mathbb{R}$ is a polynomial of degree at most $d$ in the distribution-free testing model. Here, the distance between functions is measured with respect to an unknown distribution $\mathcal{D}$ over $\mathbb{R}^n$ from which we can draw samples. In contrast ... more >>>

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere

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

Noah Fleming, Toniann Pitassi, Robert Robere

We further the study of supercritical tradeoffs in proof and circuit complexity, which is a type of tradeoff between complexity parameters where restricting one complexity parameter forces another to exceed its worst-case upper bound. In particular, we prove a new family of supercritical tradeoffs between depth and size for Resolution, ... more >>>

Noah Fleming, Toniann Pitassi

This paper surveys the development of propositional proof complexity and the seminal contributions of Alasdair Urquhart. We focus on the central role of counting principles, and in particular Tseitin's graph tautologies, to most of the key advances in lower bounds in proof complexity. We reflect on a couple of key ... more >>>

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

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

Noah Fleming, Pravesh Kothari, Toniann Pitassi

Over the last twenty years, an exciting interplay has emerged between proof systems and algorithms. Some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself. This connection has perhaps been the most consequential ... more >>>

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by

branching on an inequality and its "integer negation.'' That is, we can (nondeterministically ...
more >>>

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

The random k-SAT model is the most important and well-studied distribution over

k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for

satisfiablity algorithms, and lastly average-case hardness over this distribution has also

been linked to hardness of approximation via Feige’s hypothesis. In this ...
more >>>