Source author record

Robert Robere

Robert Robere appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Discrete Mathematics Logic in Computer Science math.CO

Catalog footprint

What is connected

5works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Further Collapses in TFNP

We show $\textsf{EOPL}=\textsf{PLS}\cap\textsf{PPAD}$. Here the class $\textsf{EOPL}$ consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubacek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse $\textsf{CLS}=\textsf{PLS}\cap\textsf{PPAD}$ by Fearnley et al. (STOC 2021). We also prove a companion result $\textsf{SOPL}=\textsf{PLS}\cap\textsf{PPADS}$, where $\textsf{SOPL}$ is the class associated with the Sink-of-Potential-Line problem.

preprint2022arXiv

Proofs, Circuits, and Communication

We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and query/communication complexity. We advocate for the theory of total search problems (TFNP) as a unifying language for these connections and discuss how this perspective suggests a whole programme for further research.

preprint2020arXiv

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open problems: * We present the first result that demonstrates a separation in proof power for cutting planes with unbounded versus polynomially bounded coefficients. Specifically, we exhibit CNF formulas that can be refuted in quadratic length and constant line space in cutting planes with unbounded coefficients, but for which there are no refutations in subexponential length and subpolynomial line space if coefficients are restricted to be of polynomial magnitude. * We give the first explicit separation between monotone Boolean formulas and monotone real formulas. Specifically, we give an explicit family of functions that can be computed with monotone real formulas of nearly linear size but require monotone Boolean formulas of exponential size. Previously only a non-explicit separation was known. An important technical ingredient, which may be of independent interest, is that we show that the Nullstellensatz degree of refuting the pebbling formula over a DAG G over any field coincides exactly with the reversible pebbling price of G. In particular, this implies that the standard decision tree complexity and the parity decision tree complexity of the corresponding falsified clause search problem are equal.

preprint2020arXiv

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph $G$ can be reversibly pebbled in time $t$ and space $s$ if and only if there is a Nullstellensatz refutation of the pebbling formula over $G$ in size $t+1$ and degree $s$ (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree trade-offs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system.

preprint2015arXiv

Path Graphs, Clique Trees, and Flowers

An \emph{asteroidal triple} is a set of three independent vertices in a graph such that any two vertices in the set are connected by a path which avoids the neighbourhood of the third. A classical result by Lekkerkerker and Boland \cite{6} showed that interval graphs are precisely the chordal graphs that do not have asteroidal triples. Interval graphs are chordal, as are the \emph{directed path graphs} and the \emph{path graphs}. Similar to Lekkerkerker and Boland, Cameron, Hoáng, and Lévêque \cite{4} gave a characterization of directed path graphs by a "special type" of asteroidal triple, and asked whether or not there was such a characterization for path graphs. We give strong evidence that asteroidal triples alone are insufficient to characterize the family of path graphs, and give a new characterization of path graphs via a forbidden induced subgraph family that we call \emph{sun systems}. Key to our new characterization is the study of \emph{asteroidal sets} in sun systems, which are a natural generalization of asteroidal triples. Our characterization of path graphs by forbidding sun systems also generalizes a characterization of directed path graphs by forbidding odd suns that was given by Chaplick et al.~\cite{9}.