Hot answers tagged

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. [2] 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