Sid Jain

On Pigeonhole Principles and Ramsey in TFNP

with Jiawei Li, Robert Robere, Zhiyang Xun

FOCS 2024

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.

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

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.

A Quantum Communication Advantage Trifecta

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

In writing

Abstract

We exhibit a total relation with an exponential separation between the weakest quantum communication model studied in literature, Quantum Simultaneous Message Passing and the strongest classical model, 2-way Randomized. Our candidate is based on the relation underlying the proof of quantumness by Yamakawa & Zhandry (JACM) and the lower bound is analyzed using a structure-vs-randomness decomposition for classical communication protocols introduced by Yang & Zhang (STOC 2024) which builds upon query-to-communication lifting machinery.

Data as a Consumable Resource

with Dar Gilboa, Jarrod McClean

ICML 2024 Workshop on Agentic Markets

Abstract

We formulate asymmetric direct sum problems in one-way communication complexity. In such problems, Alice receives one input and Bob receives m inputs. Bob's goal is to compute relations on Alice's input and each one of his inputs. We give a number of examples where the quantum communication complexity of these problems scales polynomially with m, while the classical communication complexity does not. This is motivated by the observation that data is relevant as an economic resource, especially with the prevalence of data-hungry parameterized models. But classically, data can be copied at essentially no cost without leaving a record, which is an issue for the data owner. On the other hand, our results are interpreted to say that for certain problems data behaves like a consumable resource when the owner has the ability to store and transmit data encoded in quantum states. This has potential applications to the design of data markets and competitive games involving data.

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

A Quantum Communication Advantage Trifecta

Data as a Consumable Resource

On the Rational Degree of Boolean Functions and Applications

Education

UT Austin

EPFL

IIIT-Delhi