Computational version of inverse sumset question

Question

Let $p$ be prime and $\mathbb{F}_p$ the finite field with $p$ elements. Suppose we have a set $B\subseteq \mathbb{F}_p$ satisfying $|B|<p^{\alpha}$ for some $0<\alpha<1$ and there exists $A\subseteq \mathbb{F}_p$ such that $$A+A=B$$ where $A+A$ is the sumset $$A+A=\{ a_1+a_2 \ : \ a_1,a_2\in A\}.$$ Can we calculate $A$ in time subexponential in $|B|$? The $A$ may not be unique, so any such $A$ is sufficient.

Here's an easier version of the problem where this is possible: Let $0<\alpha<1/2$. Suppose $|B|<p^{\alpha}$ satisfies $$A+C=B$$ for some $|C|<p^{\alpha}$.

If we know $B,C$ then we can recover $A$ quickly with a high probability. This follows by grouping pairs into sets $D(\lambda)$ $$D(\lambda)=\{ (b,c)\in B\times C \ : b-c=\lambda\}.$$ We then try guesses for $A$ to be made up of values $\lambda$ where $D(\lambda)$ is approximately $|D(\lambda)|\sim |C|.$ This only works with a high probability (for example, no success if $|B+B|=O(|B|)$). So another question, instead of recovering $A$ with high probability, can we recover $A$ certainly?

Answer 1

This is in fact a variation of a known problem; see, for instance, Problem 4.11 from this list by Ernie Croot and myself. Here is an algorithm which stems from an observation made there. I have not made a serious effort to estimate its running time (but see some remarks by the end of this post).

Let $B/2:=\{b/2\colon b\in B\}$; thus, $A+A=B$ implies $A\subseteq B/2$. Notice that for any pair of elements $a_1,a_2\in A$, the difference $a_1-a_2$ has at least $|A|\ge \sqrt{2|B|}-0.5$ representations as a difference of two elements of $B$; namely, the representations $$ a_1-a_2 = (a_1+a) - (a_2+a),\ a\in A. $$

Consider the graph on the vertex set $B/2$ with the vertices $b_1/2$, $b_2/2$ adjacent if and only if (i) $b_1/2+b_2/2\in B$ and, in addition, (ii) $b_1/2-b_2/2$ has at least $\sqrt{2|B|}-0.5$ representations as a difference of two elements of $B$. The maximal cliques in this graphs correspond to maximal subsets $A\subseteq B/2$ such that $A+A\subseteq B$; consequently, one can check all these maximal cliques to see, for each clique, whether for the corresponding set $A$ satisfies the equality $A+A=B$.

The running time of this algorithm is determined by the time needed to list all maximal cliques in a given graph. This is a version of the Clique Problem well-known in algorithmic graph theory. In the worst case, the time needed can be exponential in the size of the graph (as there can be exponentially many maximal cliques). However, there are improvements for the sparse graphs, and the graph constructed above is sparse (it has at most $(|B|^2/2)/\sqrt{2|B|}=O(|B|^{3/2})$ edges).