19 citations · 25 across the 4 of their papers we have counts for
4 papers
The List-Decoding Size of Reed-Muller Codes
Tali Kaufman, Shachar Lovett
In this work we study the list-decoding size of Reed-Muller codes. Given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller…
Worst Case to Average Case Reductions for Polynomials
Tali Kaufman, Shachar Lovett
A degree- polynomial in variables over a field $\F$ is {\em equidistributed} if it takes on each of its $|\F|$ values close to equally often, and {\em biased} otherwise.…
Lower bounds for adaptive linearity tests
Shachar Lovett
Linearity tests are randomized algorithms which have oracle access to the truth table of some function f, and are supposed to distinguish between linear functions and functions whi…
Inverse Conjecture for the Gowers norm is false
Shachar Lovett, Roy Meshulam, Alex Samorodnitsky
Let be a fixed prime number, and be a large integer. The 'Inverse Conjecture for the Gowers norm' states that if the "-th Gowers norm" of a function $f:\F_p^N \to \F_p$…