Provides characterization of near-extremizers for the fourth noncommutative Gowers uniformity norm, enabling an efficient tester for the third Clifford hierarchy level.
A quantitative inverse theorem for the $U^4$ norm over finite fields
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
abstract
A remarkable result of Bergelson, Tao and Ziegler implies that if $c>0$, $k$ is a positive integer, $p\geq k$ is a prime, $n$ is sufficiently large, and $f:\mathbb F_p^n\to\mathbb C$ is a function with $\|f\|_\infty\leq 1$ and $\|f\|_{U^k}\geq c$, then there is a polynomial $\pi$ of degree at most $k-1$ such that $\mathbb E_xf(x)\omega^{-\pi(x)}\geq c'$, where $\omega=\exp(2\pi i/p)$ and $c'>0$ is a constant that depends on $c,k$ and $p$ only. A version of this result for low-characteristic was also proved by Tao and Ziegler. The proofs of these results do not yield a lower bound for $c'$. Here we give a different proof in the high-characteristic case when $k=4$, which enables us to give an explicit estimate for $c'$. The bound we obtain is roughly doubly exponential in the other parameters.
verdicts
UNVERDICTED 4representative citing papers
The Jamneshan-Tao conjecture holds for finite abelian groups of rank at most R via an inverse theorem linking non-trivial Gowers norms to bounded-complexity nilsequences.
A reduction from weak agnostic learning of class C to efficient tomography of states with bounded l1-extent w.r.t. C, with a concrete algorithm for stabilizer states running in poly(n, (ξ/ε)^log(ξ/ε)) time.
Direct combinatorial proof with improved bounds that dense transverse sets contain bilinear varieties of bounded codimension.
citing papers explorer
-
On Clifford hierarchy testing and near-extremizers of noncommutative uniformity norms
Provides characterization of near-extremizers for the fourth noncommutative Gowers uniformity norm, enabling an efficient tester for the third Clifford hierarchy level.
-
The Jamneshan-Tao conjecture for finite abelian groups of bounded rank
The Jamneshan-Tao conjecture holds for finite abelian groups of rank at most R via an inverse theorem linking non-trivial Gowers norms to bounded-complexity nilsequences.
-
Tomography of quantum states with bounded extent
A reduction from weak agnostic learning of class C to efficient tomography of states with bounded l1-extent w.r.t. C, with a concrete algorithm for stabilizer states running in poly(n, (ξ/ε)^log(ξ/ε)) time.
-
A note on transverse sets and bilinear varieties
Direct combinatorial proof with improved bounds that dense transverse sets contain bilinear varieties of bounded codimension.