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

  • $\begingroup$ Is 1.5 just "the canonical" number between 1 and 2, or did you have some more convenient reason for picking that number? ​ ​ $\endgroup$ – user6973 Dec 31 '16 at 8:15
  • $\begingroup$ Its a simple, nice target to aim for. $\endgroup$ – kodlu Dec 31 '16 at 10:13
  • $\begingroup$ 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). $\endgroup$ – D.W. Jan 1 '17 at 5:16
  • $\begingroup$ @D.W. I'll have a look at those references. $\endgroup$ – kodlu Jan 1 '17 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.