50 citations · 140 across the 23 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
quant-ph2021★ 5 cited
On Certified Randomness from Fourier Sampling or Random Circuit Sampling
Roozbeh Bassirian, Adam Bouland, Bill Fefferman +2
Certified randomness has a long history in quantum information, with many potential applications. Recently Aaronson (2018, 2020) proposed a novel public certified randomness protoc…
cs.DS2021★ 1 cited
Junta Distance Approximation with Sub-Exponential Queries
Vishnu Iyer, Avishay Tal, Michael Whitmeyer
Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different results pertaining to the \emph{tolerant testing} of juntas. Given black-box access to a Boolean func…
cs.CC2021
Fourier Growth of Parity Decision Trees
Uma Girish, Avishay Tal, Kewen Wu
We prove that for every parity decision tree of depth on variables, the sum of absolute values of Fourier coefficients at level is at most $d^{\ell/2} \cdot O(\ell \…