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, 2016 at 8:15
  • $\begingroup$ Its a simple, nice target to aim for. $\endgroup$
    – kodlu
    Dec 31, 2016 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, 2017 at 5:16
  • $\begingroup$ @D.W. I'll have a look at those references. $\endgroup$
    – kodlu
    Jan 1, 2017 at 22:49


Your Answer

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