Robert Robere

STOC Conference 2024 Conference Paper

Black-Box PPP Is Not Turing-Closed

• Noah Fleming
• Stefan Grosser
• Toniann Pitassi
• Robert Robere

The complexity class PPP contains all total search problems many-one reducible to the Pigeon problem, where we are given a succinct encoding of a function mapping n +1 pigeons to n holes, and must output two pigeons that collide in a hole. PPP is one of the “original five” syntactically-defined subclasses of TFNP , and has been extensively studied due to the strong connections between its defining problem — the pigeonhole principle — and problems in cryptography, extremal combinatorics, proof complexity, and other fields. However, despite its importance, PPP appears to be less robust than the other important TFNP subclasses. In particular, unlike all other major TFNP subclasses, it was conjectured by Buss and Johnson that PPP is not closed under Turing reductions , and they called for a black-box separation in order to provide evidence for this conjecture. The question of whether PPP contains its Turing closure was further highlighted by Daskalakis in his recent IMU Abacus Medal Lecture. In this work we prove that PPP is indeed not Turing-closed in the black-box setting, affirmatively resolving the above conjecture and providing strong evidence that PPP is not Turing-closed. In fact, we are able to separate PPP from its non-adaptive Turing closure, in which all calls to the Pigeon oracle must be made in parallel. This differentiates PPP from all other important TFNP subclasses, and especially from its closely-related subclass PWPP — defined by reducibility to the weak pigeonhole principle — which is known to be non-adaptively Turing-closed. Our proof requires developing new tools for PPP lower bounds, and creates new connections between PPP and the theory of pseudoexpectation operators used for Sherali-Adams and Sum-of-Squares lower bounds. In particular, we introduce a new type of pseudoexpectation operator that is precisely tailored for lower bounds against black-box PPP , which may be of independent interest.

FOCS Conference 2024 Conference Paper

On Pigeonhole Principles and Ramsey in TFNP

• Siddhartha Jain 0002
• Jiawei Li 0014
• Robert Robere
• Zhiyang Xun

We show that the TFNP problem Ramsey is not black-box reducible to Pigeon, refuting a conjecture of Goldberg and Papadimitriou in the black-box setting. We prove this by giving reductions to Ramsey from a new family of TFNP problems that correspond to generalized versions of the pigeonhole principle, and then proving that these generalized versions cannot be reduced to Pigeon. Formally, we define $t$ -PPP as the class of total NP-search problems reducible to finding a $t$ -collision in a mapping from $(t-1) N + 1$ pigeons to $N$ holes. These classes are closely related to multi-collision resistant hash functions in cryptography. We show that the generalized pigeonhole classes form a hierarchy as $t$ increases, and also give a natural condition on the parameters $t_{1}, t_{2}$ that captures exactly when $t_{1}$ -PPP and $t_2$ -PPP collapse in the black-box setting. Finally, we prove other inclusion and separation results between these generalized Pigeon problems and other previously studied TFNP subclasses, such as PLS, PPA, and PLC. Our separation results rely on new lower bounds in propositional proof complexity based on pseudoexpectation operators, which may be of independent interest.

FOCS Conference 2022 Conference Paper

Separations in Proof Complexity and TFNP

• Mika Göös
• Alexandros Hollender
• Siddhartha Jain 0002
• Gilbert Maystre
• William Pires
• Robert Robere
• Ran Tao 0013

It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show 1, however, that any such simulation needs to exploit huge coefficients: Resolution cannot be efficiently simulated by SA when the coefficients are written in unary. We also show that Reversible Resolution (a variant of MaxSAT Resolution) cannot be efficiently simulated by Nullstellensatz (NS). These results have consequences for total NP search problems. First, we characterise the classes PPADS, PPAD, SOPL by unary-SA, unary-NS, and Reversible Resolution, respectively. Second, we show that, relative to an oracle, PLS $\nsubseteq$ PPP, SOPL $\nsubseteq$ PPA, and EOPL $\nsubseteq$ UEOPL. In particular, together with prior work, this gives a complete picture of the black-box relationships between all classical TFNP classes introduced in the 1990s. 1 This is an extended abstract. For the full version of this article, please refer to [GHJ+22b].

FOCS Conference 2021 Conference Paper

Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms

• 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), divided by $m$, as $m\rightarrow\infty$. We prove a general duality theorem that characterizes the amortized circuit complexity in terms of “formal complexity measures”. More precisely, we prove that the amortized circuit complexity in any circuit model composed out of gates from a finite set is equal to the pointwise maximum of the family of “formal complexity measures” associated with $\mathcal{F}$. Our duality theorem captures many of the formal complexity measures that have been previously studied in the literature for proving lower bounds (such as formula complexity measures, submodular complexity measures, and branching program complexity measures), and thus gives a characterization of formal complexity measures in terms of circuit complexity. We also introduce and investigate a related notion of catalytic circuit complexity, which we show is “intermediate” between amortized circuit complexity and standard circuit complexity, and which we also characterize (now, as the best integer solution to a linear program). Finally, using our new duality theorem as a guide, we strengthen the known upper bounds for non-uniform catalytic space, introduced by Buhrman et. al [1] (this is related to, but not the same as, our notion of catalytic circuit size). Potechin [2] proved that for any boolean function $f: \{0, 1\}^{n}\rightarrow\{0, 1\}$, there is a catalytic branching program computing $m=2^{2^{n}-1}$ copies of $f$ with total size $O(mn)$ -that is, linear size per copy — refuting a conjecture of Girard, Koucký and McKenzie [3]. Potechin then asked if the number of copies $m$ can be reduced while retaining the amortized upper bound. We make progress on this question by showing that if $f$ has degree $d$ when represented as polynomial over $\mathbb{F}_{2}$, then there is a catalytic branching program computing $m=2^{\begin{pmatrix}n\\ \leq d\end{pmatrix}}$ copies of $f$ with total size $O(mn)$.

STOC Conference 2021 Conference Paper

Automating algebraic proof systems is NP-hard

• Susanna F. de Rezende
• Mika Göös
• Jakob Nordström
• Toniann Pitassi
• Robert Robere
• Dmitry Sokolov 0001

FOCS Conference 2020 Conference Paper

KRW Composition Theorems via Lifting

• Susanna F. de Rezende
• Or Meir
• Jakob Nordström
• Toniann Pitassi
• Robert Robere

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i. e. , P\nsubseteq NC 1 ). Karchmer, Raz, and Wigderson [13] suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions f◇g. They showed that the validity of this conjecture would imply that P\nsubseteq NC 1. Several works have made progress toward resolving this conjecture by proving special cases. In particular, these works proved the KRW conjecture for every outer function, but only for few inner functions. Thus, it is an important challenge to prove the KRW conjecture for a wider range of inner functions. In this work, we extend significantly the range of inner functions that can be handled. First, we consider the monotone version of the KRW conjecture. We prove it for every monotone inner function whose depth complexity can be lower bounded via a query-to-communication lifting theorem. This allows us to handle several new and well-studied functions such as the s-t-connectivity, clique, and generation functions. In order to carry this progress back to the non-monotone setting, we introduce a new notion of semi-monotone composition, which combines the non-monotone complexity of the outer function with the monotone complexity of the inner function. In this setting, we prove the KRW conjecture for a similar selection of inner functions, but only for a specific choice of the outer function f.

FOCS Conference 2020 Conference Paper

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

• Susanna F. de Rezende
• Or Meir
• Jakob Nordström
• Toniann Pitassi
• Robert Robere
• Marc Vinyals

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 three 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. : We give the strongest separation to-date between monotone Boolean formulas and monotone Boolean circuits. Namely, we show that the classical GEN problem, which has polynomial-size monotone Boolean circuits, requires monotone Boolean formulas of size 2 Ω(n/polylog(n)). 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. This is an extended abstract. The full version of the paper is available at https: //arxiv. org/abs/2001. 02144.

STOC Conference 2018 Conference Paper

Lifting nullstellensatz to monotone span programs over any field

• 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 characteristic, and the first exponential separation between monotone span programs over arbitrary fields and monotone circuits. We also show tight quasipolynomial lower bounds on monotone span programs computing directed st-connectivity over arbitrary fields, separating monotone span programs from non-deterministic logspace and also separating monotone and non-monotone span programs over GF (2). Our results yield the same lower bounds for linear secret sharing schemes due to the previously known relationship between monotone span programs and linear secret sharing. To prove our characterization we introduce a new and general tool for lifting polynomial degree to rank over arbitrary fields.

FOCS Conference 2017 Conference Paper

Random Θ(log n)-CNFs Are Hard for Cutting Planes

• 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 and is a benchmark for satisfiability algorithms. We show that when k = Θ(log n), any Cutting Planes refutation for random k-SAT requires exponential size in the interesting regime where the number of clauses guarantees that the formula is unsatisfiable with high probability.

STOC Conference 2017 Conference Paper

Strongly exponential lower bounds for monotone computation

• Toniann Pitassi
• Robert Robere

For a universal constant α > 0 we prove size lower bounds of 2 α( n ) for an explicit function in monotone NP in the following models of computation: monotone formulas, monotone switching networks, monotone span programs, and monotone comparator circuits, where n is the number of variables of the underlying function. Our lower bounds improve on the best previous bounds in each of these models, and are the best possible for any function up to constant factors in the exponent. Moreover, we give one unified proof that is short and fairly elementary.

FOCS Conference 2016 Conference Paper

Exponential Lower Bounds for Monotone Span Programs

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

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993 [1]. 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 they use non-monotone operations to compute monotone functions, in fact, the best known lower bounds are quasipolynomial for a function in (nonmonotone) P [2]. A fundamental open problem is to prove exponential lower bounds on monotone span program size for any explicit function. We resolve this open problem by giving exponential lower bounds on monotone span program size for a function in monotone P. This also implies the first exponential lower bounds for linear secret sharing schemes. Our result is obtained by proving exponential lower bounds using Razborov's rank method [3], a measure that is strong enough to prove lower bounds for many monotone models. As corollaries we obtain new proofs of exponential lower bounds for monotone formula size, monotone switching network size, and the first lower bounds for monotone comparator circuit size for a function in monotone P. We also obtain new polynomial degree lower bounds for Nullstellensatz refutations using an interpolation theorem of Pudlak and Sgall [4]. Finally, we obtain quasipolynomial lower bounds on the rank measure for the st-connectivity function, implying tight bounds for st-connectivity in all of the computational models mentioned above.

FOCS Conference 2013 Conference Paper

Average Case Lower Bounds for Monotone Switching Networks

• Yuval Filmus
• Toniann Pitassi
• Robert Robere
• Stephen A. Cook

An approximate computation of a Boolean function by a circuit or switching network is a computation in which the function is computed correctly on the majority of the inputs (rather than on all inputs). Besides being interesting in their own right, lower bounds for approximate computation have proved useful in many sub areas of complexity theory, such as cryptography and derandomization. Lower bounds for approximate computation are also known as correlation bounds or average case hardness. In this paper, we obtain the first average case monotone depth lower bounds for a function in monotone P. We tolerate errors that are asymptotically the best possible for monotone circuits. Specifically, we prove average case exponential lower bounds on the size of monotone switching networks for the GEN function. As a corollary, we separate the monotone NC hierarchy in the case of errors -- a result which was previously only known for exact computations. Our proof extends and simplifies the Fourier analytic technique due to Potechin, and further developed by Chan and Potechin. As a corollary of our main lower bound, we prove that the communication complexity approach for monotone depth lower bounds does not naturally generalize to the average case setting.