50 citations · 101 across the 15 of their papers we have counts for
6 papers · 1 filter
Exponential Correlation Bounds for Polynomials
Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee +3
We prove that the XOR of majorities on disjoint blocks of \(\ell\) bits has correlation at most \((2d/\sqrt{\ell})^k\) with every degree-\(d\) polynomial over \(\mathbb F_2\).…
Does Not Relativize
Adam Bouland, Andrew Huang, Anand Natarajan +2
We construct an oracle relative to which , resolving a long-standing open question in quantum complexity theory. Together with recent work d…
Unconditional Certified Randomness without Structure
Andrea Coladangelo, Dakshita Khurana, Saachi Mutreja +3
We obtain a certified randomness protocol in the quantum random oracle model. The protocol is non-interactive and publicly verifiable with a classical verifier, and is based on Yam…
Certified Randomness without Structure Against Shallow-Query Adversaries
Dakshita Khurana, Bhaskar Roberts, Avishay Tal
In a recent breakthrough, Yamakawa and Zhandry (J. ACM 2024) constructed a proof of quantumness in the quantum random oracle model (QROM) in which the quantum prover samples a code…
Quantum Advantage in Tolerant Junta Testing
Avishay Tal, Weiqiang Yuan
We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regi…
A Relativizing MIP for BQP
Scott Aaronson, Anand Natarajan, Avishay Tal +1
Complexity class containments involving interactive proof classes are famously nonrelativizing: although , Fortnow and Sipser showed that that there…