A Quadratic Bogolyubov Theorem and Quantum Worst-Case to Average-Case ReductionsResearch Paper
Bogolyubov's lemma says that if a set has density , then the sumset contains a linear subspace of codimension bounded in terms of . It is a basic tool of additive combinatorics, and it underlies additive-combinatorial worst-case to average-case reductions for linear maps: a point of the subspace is a sum of points…