37 citations · 46 across the 11 of their papers we have counts for
5 papers · 1 filter
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…
Fourier Growth of Communication Protocols for XOR Functions
Uma Girish, Makrand Sinha, Avishay Tal +1
The level- -Fourier weight of a Boolean function refers to the sum of absolute values of its level- Fourier coefficients. Fourier growth refers to the growth of these…
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 \…
Pseudorandom Generators for Width-3 Branching Programs
Raghu Meka, Omer Reingold, Avishay Tal
We construct pseudorandom generators of seed length that -fool ordered read-once branching programs (ROBPs) of width and length . For…
Degree and Sensitivity: tails of two distributions
Parikshit Gopalan, Rocco Servedio, Avishay Tal +1
The sensitivity of a Boolean function f is the maximum over all inputs x, of the number of sensitive coordinates of x. The well-known sensitivity conjecture of Nisan (see also Nisa…