Hot answers tagged

12 votes

Finding witness in minkowski sum of integers

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)^...
user avatar
11 votes
Accepted

Finding witness in minkowski sum of integers

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 $...
user avatar
5 votes

Finding witness in minkowski sum of integers

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 ...
user avatar
  • 4,266
3 votes
Accepted

Subquadratic 3SUM when one set is in [n^1.99]

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 \...
user avatar

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