3

Assume one had a (randomised or deterministic) algorithm with asymptotic complexity $\tilde{O}(n^{1.5})$ for the problem of finding $x,y,z\in L$ where $L$ is a list with $n$ binary vectors of dimension $d$ so that $x\oplus y=z$ holds (assuming a solution exists in the list).

If you like you can assume $n$ is exponential in $d$, and that the vectors in the list are selected uniformly at random, meaning that one would need $n\geq c ~2^{d/3}$ or some positive constant $c$ before a solution is likely to exist.

What would be the implications of such a result?

Recently there have been sub $O(n^2)$ algorithms for the integer 3SUM problem but they are still not of complexity $O(n^{2-\varepsilon})$ for $\varepsilon>0.$

There is some discussion of the 3SUM problem in the answers to the question here

Community
  • 1
kodlu
  • 2,070
  • 13
  • 23
  • Is 1.5 just "the canonical" number between 1 and 2, or did you have some more convenient reason for picking that number? ​ ​ –  Dec 31 '16 at 08:15
  • Its a simple, nice target to aim for. – kodlu Dec 31 '16 at 10:13
  • There might be implications for learning parity with noise: see Blum, Kalai, and Wasserman (STOC 2000). As a farther stretch, it's possible there might also be implications for the shortest lattice vector problem: see Ajtai, Kujmar, and Sivakumar (STOC 2001). – D.W. Jan 01 '17 at 05:16
  • @D.W. I'll have a look at those references. – kodlu Jan 01 '17 at 22:49

0 Answers0