2 citations · 3 across the 6 of their papers we have counts for
Showing 2024Show all
2 papers · 1 filter
quant-ph2024
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…
cs.CC2024★ 1 cited
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…