Sid Jain

Unambiguous DNFs and Alon-Saks-Seymour

with Mika Göös, Kaspars Balodis, Shalev Ben-David, Robin Kothari

FOCS 2021 Invited to SICOMP Special Issue

journal conference eccc arXiv talk (me)

Abstract

We exhibit an unambiguous k-DNF formula that requires CNF width almost k^2, which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon--Saks--Seymour problem in graph theory (posed in 1991), which asks: How large a gap can there be between the chromatic number of a graph and its biclique partition number? Our result is also known to imply several other improved separations in query and communication complexity.

Further Collapses in TFNP

with Mika Göös, Gilbert Maystre, Alexandros Hollender, Robert Robere, Ran Tao, William Pires

SICOMP, CCC 2022, HALG 2022

conference eccc arXiv talk (Gilbert)

Abstract

We show EOPL = PLS intersect PPAD. Here the class 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 (SODA 2017) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse CLS = PLS intersect PPAD by Fearnley et al. (STOC 2021). We also prove a companion result SOPL = PLS intersect PPADS, where SOPL is the class associated with the Sink-of-Potential-Line problem.

Separations in Proof Complexity and TFNP

with Mika Göös, Gilbert Maystre, Alexandros Hollender, Robert Robere, Ran Tao, William Pires

Journal of the ACM, FOCS 2022

conference eccc arXiv FOCS talk MIAO seminar slides long slides

Abstract

It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, 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 cannot be efficiently simulated by Nullstellensatz (NS) over the reals.
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\not\subseteq PPP, SOPL\not\subseteq PPA, and EOPL\not\subseteq UEOPL. Together with prior work, this gives a complete picture of the black-box relationships between the classical TFNP classes introduced in the 1990s.

Communication Complexity of Collision

with Mika Göös

RANDOM 2022

conference eccc arXiv talk (me) slides

Abstract

The Collision problem is to decide whether a given list of n-bit numbers (x) is 1-to-1 or 2-to-1 when promised one of them is the case. We show a polynomial randomised communication lower bound for the natural two-party version of Collision where Alice holds the first half of the bits of each x and Bob holds the second half. As an application, we also show a similar lower bound for a weak bit-pigeonhole search problem, which answers a question of Itsykson and Riazanov (CCC 2021).

On the Rational Degree of Boolean Functions and Applications

with Vishnu Iyer, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer

Manuscript

eccc arXiv

Abstract

We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions f, it is conjectured that rdeg(f) is polynomially related to deg(f), where deg(f) is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least deg(f)/2 and monotone functions have rational degree at least \sqrt{deg(f)}. We observe that both of these lower bounds are tight. In addition, we show that all read-once depth-d Boolean formulae have rational degree at least Ω(deg(f)1/d). Furthermore, we show that almost every Boolean function on n variables has rational degree at least n/2 - O(\sqrt{n}). In contrast to total functions, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model.

On Pigeonhole Principles and Ramsey in TFNP

with Jiawei Li, Robert Robere, Zhiyang Xun

Manuscript

eccc arXiv slides

Abstract

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₁, t₂ that captures exactly when t₁-PPP and t₂-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.

Siddhartha Jain

Updates

Publications

Unambiguous DNFs and Alon-Saks-Seymour

Further Collapses in TFNP

Separations in Proof Complexity and TFNP

Communication Complexity of Collision

On the Rational Degree of Boolean Functions and Applications

On Pigeonhole Principles and Ramsey in TFNP

Education

UT Austin

EPFL

IIIT-Delhi