Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Robert Robere:

TR21-035 | 13th March 2021
Robert Robere, Jeroen Zuiddam

Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms

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

TR19-128 | 24th September 2019
Anna Gal, Robert Robere

Lower Bounds for (Non-monotone) Comparator Circuits

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

TR18-163 | 18th September 2018
Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov

Adventures in Monotone Complexity and TFNP

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

TR17-165 | 3rd November 2017
Toniann Pitassi, Robert Robere

Lifting Nullstellensatz to Monotone Span Programs over Any Field

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

TR17-151 | 8th October 2017
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

Stabbing Planes

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

TR17-045 | 7th March 2017
Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

Random CNFs are Hard for Cutting Planes

Revisions: 2

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

TR16-064 | 19th April 2016
Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Exponential Lower Bounds for Monotone Span Programs

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

ISSN 1433-8092 | Imprint