← All problems

Approximate homomorphism testing conjecture

16 years old · traced to

Let f:F2n→F2mf:\mathbb{F}_2^n \to \mathbb{F}_2^m be a function, and let ϵ\epsilon measure the probability that it satisfies the additive homomorphism equation on uniformly sampled x,y∈F2nx,y \in \mathbb{F}_2^n. Approximate homomorphism testing conjecture. If

Pr⁡x,y[f(x+y)=f(x)+f(y)]≥ϵ,\Pr_{x,y}[f(x+y)=f(x)+f(y)] \ge \epsilon,

then there is a linear map ℓ:F2n→F2m\ell:\mathbb{F}_2^n \to \mathbb{F}_2^m such that

Pr⁡x[f(x)=ℓ(x)]≥ϵO(1).\Pr_x[f(x)=\ell(x)] \ge \epsilon^{O(1)}.

This is an equivalent formulation of the Polynomial Freiman–Ruzsa conjecture in the source. The paper presents it as an open polynomial quantitative strengthening of approximate homomorphism testing.

References
  1. Shachar Lovett, “Equivalence of polynomial conjectures in additive combinatorics”, arXiv:1001.3356 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.