Siddhartha Jain

Hiya! I'm a theoretical computer scientist who primarily works on quantum algorithms and complexity theory. I'm a PhD student at UT Austin, fortunate to be advised by Scott Aaronson and supported by an Amazon AI Fellowship. During my PhD, I have visited Google Quantum AI, AWS Center for Quantum Computing, Alignment Research Center, and Simons Institute for the Theory of Computing. Previously, I was a MSc student at EPFL and mentored by Mika Göös.

Updates

- I am organizing a workshop on TCS problems in Quantum Architecture and Compilation with Sunny He, Robert Huang, Robin Kothari, and Esha Swaroop at FOCS 2026!
- I am serving on the program committee for QIP 2027. Submit your best work!

Papers

What is TFNP?

TFNP has been studied since the 90s [Pap94] as a framework to classify NP-intermediate problems: problems which are not NP-hard but also not believed to be in P. Given that we believe quantum computers cannot solve NP-hard problems [BBBV97], NP-intermediate problems are prime candidates for useful quantum advantage. In fact, the most famous problem in quantum computing, FACTORING lies in TFNP.
TFNP (Total Function NP) is the complexity class of NP search problems which always have a solution. It is a search problem, which means that you recieve an input x and you want to find one of many possible y such that (x,y) is a valid input-solution pair. It is in NP which means that checking that (x,y) is valid can be done efficiently. Finally, it is total which means that given any x you are certain that there is some y such that (x,y) is a valid input-solution pair.

Credit

Authors are listed in alphabetical order in last name for most papers, which is standard in mathematics and theoretical computer science. Papers marked with an asterisk (*) use contribution order, which is standard in physics and applied areas of computer science.

Survey

1. The Compendium of Super-Quadratic Computational Quantum Advantages

   *Philipp Kammerlander, Thomas E. O'Brien, Robbie King, Rolando Somma, Mária Kieferová, Brad Lackey, Alexander Schmidhuber, Siddhartha Jain, Andi Gu, Yuri Alexeev, Shouvanik Chakrabarti, Ruslan Shaydulin, Pietro M. Posta, Guang Hao Low, Dar Gilboa, Matthias Troyer, Barry C. Sanders, Matthias Christandl, Elica Kyoseva, Catherine Lefebvre, Ryan Babbush

   Preprint
   

   arXiv

   Abstract

   This compendium presents a structured collection of computational problems with credible prospects for realizing meaningful quantum advantage, focused on describing problem characteristics rather than specific algorithms. It is intended for non-quantum researchers and practitioners with strong computational backgrounds, particularly domain experts, seeking to assess the relevance of quantum methods to real-world problems. The compendium focuses on enumerating core problems for which there is good evidence that a quantum computer can realize more than a quadratic speedup in offline non-relativized time-complexity (e.g., as opposed to in oracular settings, streaming models, or communication advantages). Entries characterize the structural constraints that real-world instances must satisfy to realize those advantages in practice. The intention is to provide a reference that can be leveraged to connect quantum algorithms to practical use cases.

Quantum computing

11. Scalable Passive QRAM

    *Siddhartha Jain, Alexander Dalzell, Connor Hann

    Preprint
    

    arXiv

    Abstract

    We present a blueprint for implementing the physical QRAM operation in a scalable, passive manner, proving its feasibility in principle. Our construction is passive because for an n-qubit address over N = 2ⁿ memory bits the energy cost per QRAM query is O(log N), and to our knowledge it is the first construction to use polylog N energy. The runtime for each query is O(log² N). It is achieved by evolving a pre-manufactured time-independent 4-local Hamiltonian with O(N) terms where every qubit participates in at most 4 terms.

12. Exponential quantum space advantage in random data streams

    Adam Bouland, Matthew Ding, Siddhartha Jain

    Preprint
    

    arXiv

    Abstract

    We show two unconditional quantum space advantages in the random-order streaming model. First, we show the Yamakawa–Zhandry Code Intersection problem admits exponential quantum advantage in the streaming model when its inputs are streamed in random order. This means quantum computers exhibit exponential space advantage even when simply receiving (x, f(x)) pairs for a uniformly random function f in a uniformly random order. Our lower bound is shown using density-restoring partitions as in the work of Göös, Gur, Jain, and Li (STOC 2025) combined with a convex potential, similar to the work of Raz (J.ACM 2018) on parity learning and its generalization by Garg, Raz, and Tal (STOC 2018).
    Second, we use our framework to show quantum space advantage for the Optimal Polynomial Intersection (OPI) problem in certain regimes via a streaming version of the Decoded Quantum Interferometry algorithm (Nature 2025; arXiv:2510.10967). In particular, we show that for degree d and n evaluation points, attaining 1/2 + Ω(√(d/n)) fraction of satisfied OPI constraints via streaming requires Ω(n) classical bits of memory but only O(d log n) qubits. This yields provable quantum advantage in a "low-rate" regime when the number of evaluation points is much larger than the degree, with a space advantage that can be as large as exponential in certain parameter settings.

13. Certified Randomness with Optimal Rate

    Siddhartha Jain, Saachi Mutreja, Bhaskar Roberts

    Preprint
    

    arXiv

    Abstract

    The generation of certified random bits is an emerging near-term application of quantum computers. Potential applications, such as randomness beacons and CRS generation, require nearly uniform randomness, whose rate (the ratio of min-entropy to bitlength) is ~ 1. However, existing protocols for certified randomness either produce weakly random strings with rate o(1), or they require a trusted random seed.
    We show how to certify randomness with the optimal rate ~ 1 without requiring any trusted randomness from the verifier. Our protocol is secure unconditionally in the quantum random oracle model (QROM). This improves the result of Coladangelo et al., who certified weakly random strings unconditionally in the QROM, and answers a question posed by Aaronson and Hung.
    We also define and construct a proof of conditional min-entropy, which certifies optimal min-entropy even conditioned on an adversarially chosen transcript. We show an application of this primitive to randomness beacons, where each pulse should have high min-entropy conditioned on all previous messages.

14. Ramanujan quantum expanders from the Weil representation

    Siddhartha Jain

    Preprint
    

    arXiv

    Abstract

    For every odd prime power q and D = q+1, we construct an infinite family of Ramanujan quantum expanders of degree D. The construction transfers Morgenstern's Ramanujan Cayley graphs on PSL₂(𝔽_p) for p which is an even power of q, through the odd irreducible subrepresentation of the Weil representation of SL₂(𝔽_p). For a quantum expander of dimension N, our implementation uses O(log² N) elementary gates, and O(log N) ancilla qudits, using a fixed finite gate set depending on q. An advantage compared to the previous work of Iyer, Jain, Jordan, and Somma (FOCS 2026) is that assuming the quantum circuit is implemented exactly, we satisfy the 2√(D-1)/D singular value bound exactly without any additive error.

15. Decentralized Consensus from Quantum Proof of Position

    Dar Gilboa, Siddhartha Jain, Or Sattath

    Preprint
    

    arXiv

    Abstract

    We construct an energy efficient consensus protocol with geospatial position as an external resource by using quantum computers. Economic resources of some form are essential in decentralized consensus protocols in order to prevent attacks in which malicious parties costlessly generate fake identities.
    The resulting protocol, Quantum Proof of Position (QPoP), improves on existing classical mechanisms: it dispenses with the notorious electricity consumption of Proof-of-Work, and, because its resource is external to the protocol, with the wealth concentration of Proof-of-Stake. QPoP also has two properties that, to our knowledge, no other permissionless Sybil resistance mechanism possesses. First, its Sybil resistance is non-rival: position verification occupies a quantum computer only briefly, so a single device can secure any number of chains at once, each enjoying its full benefit. Second, the protocol generates geographic decentralization, because its resource cannot be agglomerated: a participant's power is the number of distinct locations at which it operates a quantum computer, and a second computer at an occupied location adds nothing.

16. Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders

    Vishnu Iyer, Siddhartha Jain, Stephen Jordan, Rolando Somma

    FOCS 2026, TQC 2026
    

    eccc arXiv Stanford slides

    Abstract

    We present efficient quantum circuits that implement high-dimensional unitary irreducible representations (irreps) of SU(n), where n>=2 is constant. For dimension N and error ϵ, the number of quantum gates in our circuits is polynomial in log(N) and log(1/ϵ). Our construction relies on the Jordan-Schwinger representation, which allows us to realize irreps of SU(n) in the Hilbert space of n quantum harmonic oscillators. Together with a recent efficient quantum Hermite transform, which allows us to map the computational basis states to the eigenstates of the quantum harmonic oscillator, this allows us to implement these irreps efficiently. Our quantum circuits can be used to construct explicit Ramanujan quantum expanders, a longstanding open problem. They can also be used to fast-forward the evolution of certain quantum systems.

17. Efficient Quantum Hermite Transform

    *Siddhartha Jain, Vishnu Iyer, Rolando Somma, Ning Bao, Stephen Jordan

    STOC 2026, QIP 2026
    

    conference eccc arXiv QIP slides kudos

    Abstract

    We present a new primitive for quantum algorithms that implements a discrete Hermite transform efficiently, in time that depends logarithmically in both the dimension and the inverse of the allowable error. This transform, which maps basis states to states whose amplitudes are proportional to the Hermite functions, can be interpreted as the Gaussian analogue of the Fourier transform. Our algorithm is based on a method to exponentially fast forward the evolution of the quantum harmonic oscillator, which significantly improves over prior art. We apply this Hermite transform to give examples of provable quantum query advantage in property testing and learning. In particular, we show how to efficiently test the property of being close to a low- degree in the Hermite basis when inputs are sampled from the Gaussian distribution, and how to solve a Gaussian analogue of the Goldreich-Levin learning task efficiently. We also comment on other potential uses of this transform to simulating time dynamics of quantum systems in the continuum.

    Summary (for non-specialists)

    The Fourier Transform is a fundamental tool in computer science, signal processing and physics. It transforms signals into their frequency components, and is used in applications ranging from image compression to solving differential equations. The Fourier Transform can be efficiently implemented on a quantum computer using the Quantum Fourier Transform (QFT), which is a key component of Shor's algorithm for factoring large numbers. In this work we present an efficient analogue of this algorithmic primitive for the Hermite functions, which are central to many physical systems in the continuum.
    Devising such an efficient algorithm required settling the computational complexity of simulating the quantum harmonic oscillator, which is a fundamental model in quantum mechanics. We show how to simulate this system in barely more time than it takes to read the input, giving a nearly optimal circuit for this task four decades after Richard Feynman [Fey82] posed the simulation of quantum physical systems as a key application of quantum computers.
    

    Follow-up

    This work was used in multiple follow-ups to get new algorithmic primitives, including efficient algorithms for irreps of SU(2) by Iyer, Jain, Jordan, and Somma, and an efficient polaron transform for simulating fermionic-bosonic interaction by Apel and Şahinoğlu, and it was extended to efficient discrete and continuous transforms for other orthogonal polynomial families in the Askey scheme in the work of Prakash, Sureshbabu, Herman & Chakrabarti. It was also used to get fast algorithms for learning linear threshold functions by Krivcenko, Nguyen, and de Wolf.

18. Anonymous Quantum Tokens with Classical Verification

    Dmytro Gavinsky, Dar Gilboa, Siddhartha Jain, Dmitri Maslov, Jarrod McClean

    Manuscript
    

    arXiv yahoo! finance

    Abstract

    The no-cloning theorem can be used as a basis for quantum money constructions which guarantee unconditionally unforgeable currency. Existing schemes, however, either (i) require long-term quantum memory and quantum communication between the user and the bank in order to verify the validity of a bill or (ii) fail to protect user privacy due to the uniqueness of each bill issued by the bank, which can allow its usage to be tracked. We introduce a construction of single-use quantum money that gives users the ability to detect whether the issuing authority is tracking them, employing an auditing procedure for which we prove unconditional security. Bill validation is classical, and hence does not require long-term quantum memory or quantum communication, making the protocol relatively practical to deploy. We discuss potential applications beyond money, including anonymous one-time pads and voting.

19. Quantum Communication Advantage in TFNP

    Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li

    STOC 2025, QIP 2025
    

    eccc arXiv conference STOC talk (me) slides

    Abstract

    We exhibit a total search problem with classically verifiable solutions whose communication complexity in the quantum SMP model is exponentially smaller than in the classical two-way randomized model. 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.

    Summary (for non-specialists)

    We demonstrate a communication problem which can be solved in the quantum setting by using a few hundred qudits. Yet we prove that classically, any protocol must communicate more bits than there are atoms in the observable universe.
    In communication complexity, Alice and Bob recieve inputs x and y and they want to compute a known function which depends on both x and y while communicating as few (qu)bits as possible. Simulatenous message passing (SMP) is a very restricted form of communication where they are not allowed to interact with each other at all and just send a single message to a referee who computes the answer. Our protocol works in the quanutm SMP model, and we prove a lower bound in the vanilla model of classical communication where there are no restrictions placed on Alice and Bob. A crucial feature of our result is also that our problem is classically verifiable, so even if the quantum communication & computation is untrusted the final output can be checked efficiently.

20. Consumable Data via Quantum Communication

    *Dar Gilboa, Siddhartha Jain, Jarrod McClean

    RANDOM 2025, ICML 2024 Workshop on Agentic Markets
    

    eccc arXiv conference OpenReview UPenn Econ slides

    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.

    Other venues

    Presented at the UPenn Economics conference on Quantum Computing Applications in Economics and Finance.

21. Communication Complexity of Collision

    Mika Göös, Siddhartha Jain

    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 for classical protocols. The correct exponent remains open for quantum protocols, the best lower bound still being 1/12 from this paper, while the upper bound is 1/6. For one-way quantum communication, the lower bound was improved to a tight exponent of 1/4 by Gao, Liu, Yang, and Zhang.

    Summary (for non-specialists)

    We study a natural problem in communication complexity where Alice and Bob want to check if their shared list of numbers has repeated elements (collisions) or not. Our results are useful in cryptography.
    In communication complexity, Alice and Bob recieve inputs x and y and they want to compute a known function which depends on both x and y while communicating as few bits as possible. We study the problem where we have a list of n-bit numbers which are either all unique or every number is repated twice. Alice recieves the first half of every number and Bob recieves the second half, and they want to decide which is the case. We prove the first non-trivial lower bound for this problem, which has an application cryptography. In particular, it shows that it is possible to build a pair of hash functions for which it is hard to find a collision even if each function in the pair can be accessed through a backdoor by some adversary. These are called Backdoored Random Oracles.

Classical complexity

6. Total Search Problems in ZPP

   Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Morgan Shirley, Hanlin Ren, Weiqiang Yuan

   ITCS 2026
   

   eccc arXiv

   Abstract

   We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between N and 2N), refuter problems for many circuit lower bounds, and Lossy-Code (Korten, CCC 2022). The Lossy-Code problem has found prominence due to its fundamental connections to derandomization, catalytic computing, and the metamathematics of complexity theory, among other areas.
   While TFZPP collapses to FP under standard derandomization assumptions in the white-box setting, we are able to separate TFZPP from the major TFNP subclasses in the black-box setting. In fact, we are able to separate it from every uniform TFNP class under a standard conjecture. To do so, we extend the connection between proof complexity and black-box TFNP to randomized proof systems and randomized reductions.
   Next, we turn to developing a taxonomy of TFZPP problems. We highlight a problem called Nephew, originating from an infinity axiom in set theory. We show that Nephew is in PWPP \cap TFZPP and conjecture that it is not reducible to Lossy-Code. Intriguingly, except for some artificial examples, most other black-box TFZPP problems that we are aware of reduce to Lossy-Code:

   • We define a problem called Empty-Child capturing finding a leaf in a rooted binary tree, and show that this problem is equivalent to Lossy-Code. We also show that a variant of Empty-Child with heights is complete for the intersection of SOPL and Lossy-Code.
   • We strengthen Lossy-Code with several combinatorial inequalities such as the AM-GM inequality. We show the resulting new problems are still reducible to Lossy-Code. These results are proved by formalizations in bounded arithmetic, specifically in Jerabek's theory APC₁.
   • Finally, we show that the Dense-Linear-Ordering problem reduces to Lossy-Code.

7. On Pigeonhole Principles and Ramsey in TFNP

   Siddhartha Jain, 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.

   Summary (for non-specialists)

   This paper is motivated by the metamathematical question: is there a short (efficient) proof of a complicated theorem using a simple theorem? More specifically, can Ramsey's theorem in extremal combinatorics be proved using the (simple) pigeonhole principle?
   A celebrated theorem of Frank Ramsey says that in any undirected, simple graph on 2^n vertices, there must exist a clique or independent set of size n/2. RAMSEY is the search problem of finding such a clique or independent set given a succinctly represented graph as input. Similarly, PIGEON is the search problem corresponding to the pigeonhole principle. We show that there is no black-box reduction from RAMSEY to PIGEON: finding a clique or independent set does not reduce to finding a collision. On the way to proving this, we define new problems corresponding to the generalized pigeonhole principle: if tn + 1 pigeons are put into n holes, some hole must have t+1 pigeons. We prove a structure theorem about these problems and study its relation to cryptography.

8. On the Rational Degree of Boolean Functions and Applications

   Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Robin Kothari, 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.

9. Separations in Proof Complexity and TFNP

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

   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.

   Summary (for non-specialists)

   Is every problem solvable by local search also solvable by collision-finding? We prove that the answer to this question is no, within the formalization of TFNP.
   To formalize this, PLS is the class of problems which can be solved using local search. PPP is the class of problems which can be solved by finding a collision in a compressing function. We show that there is no black-box reduction from PLS to PPP: there is no way to convert a reduction to local search into a reduction to collision-finding. This was an open question since these classes were defined almost three decades ago. Our result goes through a connection to proof complexity, which studies how long your proof needs to be if you're only allowed to use certain rules of inference.

10. Further Collapses in TFNP

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

    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.

    Summary (for non-specialists)

    We show that the complexity class EOPL contains exactly the problems which can be solved efficiently using local search and by computing market equillibria.
    Problems which can be solved using local search can be formalized to be in the complexity class PLS. Similarly, PPAD is the class of problems which have a solution due to a parity argument, and famously the problem of computing a Nash Equillibirum is complete for this class. We show that a problem called End-of-Potential-Line is complete for their intersection: problem A reduces to EOPL if and only if it lies in both PLS and PPAD. As a corollary of this work, we give a simple combinatorial proof of the fact the the class CLS (problems which can be solved using gradient descent) is also equal to this intersection.

11. Unambiguous DNFs and Alon-Saks-Seymour

    Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, 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.

    Summary (for non-specialists)

    We answer a long-standing open problem in graph theory via reductions to questions in query and communication complexity. We do not know of a way to rephrase our proof in the language of graph theory or combinatorics, so this is an example of techniques in computer science being useful for pure math. For this reason, Noga Alon mentioned our work in his Knuth Prize lecture.
    Alon--Saks--Seymour refers to a line of work in graph theory where the goal is to understand how much larger one property of the graph (chromatic number) can be than another property (biclique partition number). Figuring out the exact relationship was known to be equivalent to figuring out the communication complexity of the "clique vs independent set" problem. In communication complexity, Alice and Bob recieve inputs x and y and they want to compute a known function which depends on both x and y while communicating as few bits as possible. In this paper, we resolve the communication complexity of clique vs independent set when Alice and Bob recieve some additional help from a third-party prover, which essentially answers the Alon--Saks--Seymour problem in combinatorics when considering arbitrary graphs.

Experience

Education