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.

Interesting links: ECCC Fixes, Where's That Paper?


Publications

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.

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.

Separations in Proof Complexity and TFNP

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.

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

On the Rational Degree of Boolean Functions and Applications

Preprint
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
Preprint
Abstract The generalized pigeonhole principle says that if tN + 1 pigeons are put into N holes then there must be a hole containing at least t+1 pigeons. Let t-PPP denote the class of all total NP-search problems reducible to finding such a t-collision of pigeons. We introduce a new hierarchy of classes defined by the problems t-PPP. In addition to being natural problems in TFNP, we show that classes in and above the hierarchy are related to the notion of multi-collision resistance in cryptography, and contain the problem underlying the breakthrough average-case quantum advantage result shown by Yamakawa & Zhandry (FOCS 2022).
Finally, we give lower bound techniques for the black-box versions of t-PPP for any t. In particular, we prove that Ramsey is not in t-PPP, for any t that is sub-polynomial in log(N), in the black-box setting. Goldberg and Papadimitriou conjectured that Ramsey reduces to 2-PPP, we thus refute it and more in the black-box setting. We also provide an ensemble of black-box separations which resolve the relative complexity of the t-PPP classes with other well-known TFNP classes.

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

-->