Research proof index

Honest Alice has error ≥ e with probability ≤ q

Alice makes few queries, regardless of Bob and Vera

Alice produces (p,y) with p close to o.probs y with good probability

Alice produces (p,y) with p close and y true with good probability, since if we condition on Alice being close she does as least as well as a close oracle.

An approximate-homomorphism theorem for finite elementary abelian $2$-groups. Let $f:G\to G'$ and $K>0$. If at least a proportion $K^{-1}$ of pairs $(x,y)\in G^2$ satisfy $f(x+y)=f(x)+f(y)$, then there are an additive homomorphism $\varphi:G\to G'$ and a constant $c\in G'$ such that $f(x)=\varphi(x)+c$ for at least $|G|/(2^{144}K^{122})$ values of $x$.

If $A \subset {\bf F}_2^n$ is finite non-empty with $|A+A| \leq K|A|$, then there exists a subgroup $H$ of ${\bf F}_2^n$ with $|H| \leq |A|$ such that $A$ can be covered by at most $2K^9$ translates of $H$.