Shachar Lovett

most citedWorst Case to Average Case Reductions for Polynomials

19 citations · 25 across the 4 of their papers we have counts for

collaborators

Showing math.COShow all

2 papers · 1 filter

math.CO2008★ 19 cited

Worst Case to Average Case Reductions for Polynomials

Tali Kaufman, Shachar Lovett

A degree- $d$ polynomial $p$ in $n$ 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.…

math.CO2007★ 1 cited

Inverse Conjecture for the Gowers norm is false

Shachar Lovett, Roy Meshulam, Alex Samorodnitsky

Let $p$ be a fixed prime number, and $N$ be a large integer. The 'Inverse Conjecture for the Gowers norm' states that if the " $d$ -th Gowers norm" of a function $f:\F_p^N \to \F_p$…