5 citations · 5 across the 1 of their papers we have counts for
3 papers
cs.LG2023
Tight Time-Space Lower Bounds for Constant-Pass Learning
Xin Lyu, Avishay Tal, Hongxun Wu +1
In his breakthrough paper, Raz showed that any parity learning algorithm requires either quadratic memory or an exponential number of samples [FOCS'16, JACM'19]. A line of work tha…
cs.CC2023
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…
cs.CC2014★ 5 cited
Two Structural Results for Low Degree Polynomials and Applications
Gil Cohen, Avishay Tal
In this paper, two structural results concerning low degree polynomials over finite fields are given. The first states that over any finite field , for any polynomial $…