Sid Jain

On Pigeonhole Principles and Ramsey in TFNP

with Jiawei Li, Robert Robere, Zhiyang Xun

FOCS 2024

eccc arXiv FOCS talk (me) slides long 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.

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

Follow-up

The exponent 1/12 in our lower bound was improved to a tight exponent of 1/4 by Yang & Zhang.

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

journal conference eccc arXiv FOCS talk (me) 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.

Further Collapses in TFNP

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

SICOMP, CCC 2022, HALG 2022

journal conference eccc arXiv talk (G.M.)

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.

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.

Follow-up

Our graph-theoretic result was used to show that partial concept classes cannot be represented by total concept classes of small dimension in the work of Alon, Hanneke, Holzman & Moran.

Quantum Communication Advantage in TFNP

with Mika Göös, Tom Gur, Jiawei Li

In writing

Abstract

We exhibit a total two-party search problem for which the communication complexity in the Quantum Simultaneous Message Passing model is exponentially smaller than in the classical two-way randomized model. Our problem is a two-party analogue of the Yamakawa--Zhandry problem (JACM 2024), and our lower bound is analysed via the structure-vs-randomness decomposition of classical communication protocols. Our problem has the additional properties of being efficiently verifiable (in TFNP) and computationally efficient.

Consumable Data via Quantum Communication

with Dar Gilboa, Jarrod McClean

ICML 2024 Workshop on Agentic Markets

eccc arXiv

Abstract

Classical data can be copied and re-used for computation, with adverse consequences economically and in terms of data privacy. Motivated by this, we formulate problems in one-way communication complexity where Alice holds some data and Bob holds m inputs, and he wants to compute m instances of a bipartite relation on Alice's data and each of his inputs. We call this the asymmetric direct sum question for one-way communication. We give a number of examples where the quantum communication complexity of such problems scales polynomially with m, while the classical communication complexity depends at most logarithmically on m. For these examples, data behaves like a consumable resource when the owner stores and transmits it as quantum states. We show an application to a strategic data-selling game, and discuss other potential economic implications.

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.

Siddhartha Jain

Papers

Publications

On Pigeonhole Principles and Ramsey in TFNP

Communication Complexity of Collision

Separations in Proof Complexity and TFNP

Further Collapses in TFNP

Unambiguous DNFs and Alon-Saks-Seymour

Manuscripts

Quantum Communication Advantage in TFNP

Consumable Data via Quantum Communication

On the Rational Degree of Boolean Functions and Applications

Education

UT Austin

EPFL

IIIT-Delhi