Siddhartha Jain

Gates-Dell Complex, 4.410E · Austin, TX 78712
[email protected]

Hiya! I'm a PhD student at UT Austin, fortunate to be advised by Scott Aaronson. Previously, I was a MSc student at EPFL and lucky to be mentored by Mika Göös.
Curriculum Vitae.


Papers

Publications

On Pigeonhole Principles and Ramsey in TFNP

with Jiawei Li, Robert Robere, Zhiyang Xun
FOCS 2024
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 t1, t2 that captures exactly when t1-PPP and t2-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

RANDOM 2022
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

Journal of the ACM, FOCS 2022
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

SICOMP, CCC 2022, HALG 2022
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

FOCS 2021 Invited to SICOMP Special Issue
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-upOur 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.

Manuscripts

Quantum Communication Advantage in TFNP

Preprint
Abstract We exhibit a total search problem whose communication complexity in the quantum SMP (simultaneous message passing) model is exponentially smaller than in the classical two-way randomized model. Moreover, the quantum protocol is computationally efficient and its solutions are classically verifiable, that is, the problem lies in the communication analogue of the class TFNP. Our problem is a bipartite version of a query complexity problem recently introduced by Yamakawa and Zhandry (JACM 2024). We prove the classical lower bound using the structure-vs-randomness paradigm for analyzing communication protocols.

Consumable Data via Quantum Communication

ICML 2024 Workshop on Agentic Markets
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

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

Education

UT Austin

Doctor of Philosophy
Computer Science
2022 - Present

EPFL

Master of Science
Computer Science
2020 - 2022

IIIT-Delhi

Bachelor of Technology
Computer Science & Applied Mathematics
  • Co-founded the Math club (Évariste)
2016 - 2020

-->