2 citations · 3 across the 6 of their papers we have counts for
9 papers
Certified Randomness with Optimal Rate
Siddhartha Jain, Saachi Mutreja, Bhaskar Roberts
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 ne…
Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
Vishnu Iyer, Siddhartha Jain, Stephen Jordan +1
We present efficient quantum circuits that implement high-dimensional unitary irreducible representations (irreps) of , where is constant. For dimension and er…
Efficient Quantum Hermite Transform
Siddhartha Jain, Vishnu Iyer, Rolando D. Somma +2
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 inver…
Quantum Communication Advantage in TFNP
Mika Göös, Tom Gur, Siddhartha Jain +1
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-w…
On Pigeonhole Principles and Ramsey in TFNP
Siddhartha Jain, Jiawei Li, Robert Robere +1
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 red…
On the Rational Degree of Boolean Functions and Applications
Vishnu Iyer, Siddhartha Jain, Robin Kothari +5
We study a natural complexity measure of Boolean functions known as the rational degree. Denoted , it is the minimal degree of a rational function that is equal t…
Communication Complexity of Collision
Mika Göös, Siddhartha Jain
The Collision problem is to decide whether a given list of numbers is -to- or -to- when promised one of them is the case. We show an $n^{Ω(1)…
Separations in Proof Complexity and TFNP
Mika Göös, Alexandros Hollender, Siddhartha Jain +4
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: Re…
Unambiguous DNFs and Alon-Saks-Seymour
Kaspars Balodis, Shalev Ben-David, Mika Göös +2
We exhibit an unambiguous k-DNF formula that requires CNF width , which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the…