# Tag Info

12

Ok, I've been holding off since really Sariel should get credit for an answer, but I'm tired of waiting, so here is my cut at a near-linear randomized algorithm. By choosing samples of $n(1-\epsilon)^i$ points, $i=0,1,\dots$, you can get a logarithmic number of subproblems such that each sum from the original problem has constant probability of being ...

12

There is a more general question on mathoverflow, and I asked a similar question on CS.SE. jbapple provided a good answer. To quote: "Necklaces, Convolutions, and X+Y", By Bremner et al. shows a $O\left(\frac{n^2(\lg \lg n)^3}{\lg^2 n}\right)$ algorithm for this problem on the real RAM and a $O(n \sqrt{n})$ algorithm in the nonuniform linear ...

11

Here I am explaining how to get $O(n *\mathrm{polylog} n)$ randomized running time. We need a sequence of observations: A witness of a value $v$ is a pair of numbers $(a,b) \in A \times B$ such that $a+b=v$. Let $P_A(x) = \sum_{i \in A} x^i$ and $P_B(x)$ be defined analogously. Observe that the coefficient of $x^v$ in $P_A(x) * P_B(x)$ is the number of ...

5

This answer gives a determinstic $O(n~\mathrm{polylog} n)$ algorithm. It appears that Sariel and David's algorithm can be derandomized through an approach similar to this paper.  While going through the process I found there is a more general problem that implies this result. The $k$-reconstruction problem There are hidden sets $S_1,\ldots,S_n \... 3 I think one can solve this problem as follows. Assume that we have three sets$A, B, C$of integers,$|A|=|B|=|C|=n$, and$C\subseteq [n^{2-\delta}]$. We want to check whether there exist$a\in A, b \in B, c \in C$such that$a+b+c=0$. First, we partition the set$A$into$k\leq n$sets$A_1,\ldots A_k$, where each$A_i\$ contains numbers in an interval of ...

Only top voted, non community-wiki answers of a minimum length are eligible