All reports by Author Robert Robere:

__
TR21-035
| 13th March 2021
__

Robert Robere, Jeroen Zuiddam#### Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms

__
TR19-128
| 24th September 2019
__

Anna Gal, Robert Robere#### Lower Bounds for (Non-monotone) Comparator Circuits

__
TR18-163
| 18th September 2018
__

Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov#### Adventures in Monotone Complexity and TFNP

__
TR17-165
| 3rd November 2017
__

Toniann Pitassi, Robert Robere#### Lifting Nullstellensatz to Monotone Span Programs over Any Field

__
TR17-151
| 8th October 2017
__

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

__
TR17-045
| 7th March 2017
__

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

Revisions: 2

__
TR16-064
| 19th April 2016
__

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman#### Exponential Lower Bounds for Monotone Span Programs

Robert Robere, Jeroen Zuiddam

We study the amortized circuit complexity of boolean functions.

Given a circuit model $\mathcal{F}$ and a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, the $\mathcal{F}$-amortized circuit complexity is defined to be the size of the smallest circuit that outputs $m$ copies of $f$ (evaluated on the same input), ...
more >>>

Anna Gal, Robert Robere

Comparator circuits are a natural circuit model for studying the concept of bounded fan-out computations, which intuitively corresponds to whether or not a computational model can make "copies" of intermediate computational steps. Comparator circuits are believed to be weaker than general Boolean circuits, but they can simulate Branching Programs and ... more >>>

Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov

$\mathbf{Separations:}$ We introduce a monotone variant of XOR-SAT and show it has exponential monotone circuit complexity. Since XOR-SAT is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone span programs over R can be exponentially more powerful than over finite ... more >>>

Toniann Pitassi, Robert Robere

We characterize the size of monotone span programs computing certain "structured" boolean functions by the Nullstellensatz degree of a related unsatisfiable Boolean formula.

This yields the first exponential lower bounds for monotone span programs over arbitrary fields, the first exponential separations between monotone span programs over fields of different ... 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 >>>

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993. They are known to be equivalent to linear secret sharing schemes, and have various applications in complexity theory and cryptography. Lower bounds for monotone span programs have been difficult to obtain because ... more >>>