3 papers
quant-ph2026
Distributional Variants of the Aaronson-Ambainis Conjecture
Uma Girish, Kunal Mittal, Barak Nehoran +1
A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query…
cs.CC2022
Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs
Uma Girish, Kunal Mittal, Ran Raz +1
We prove that for every 3-player (3-prover) game with value less than one, whose query distribution has the support of ham…
cs.CC2022
Parallel Repetition For All 3-Player Games Over Binary Alphabet
Uma Girish, Justin Holmgren, Kunal Mittal +2
We prove that for every 3-player game with binary questions and answers and value , the value of the -fold parallel repetition of the game decays polynomially fast to 0. Tha…