<p>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). </p>

<p>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.</p>

<p>What would be the implications of such a result?</p>

<p>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&gt;0.$</p>

<p>There is some discussion of the 3SUM problem in the answers to the question <a href="https://cstheory.stackexchange.com/questions/21948/comparing-two-algorithms-for-3sum-problem-over-integers">here</a></p>

CC BY-SA 3.0
2016-12-31T10:13:28.070Z
Its a simple, nice target to aim for.
kodlu
CC BY-SA 3.0
2017-01-01T05:16:53.200Z
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.
CC BY-SA 3.0
2017-01-01T22:49:30.463Z
@D.W. I'll have a look at those references.
kodlu
<cc.complexity-theory><time-complexity>
Implications of an $\tilde{O}(n^{1.5})$ 3XORSUM algorithm
kodlu
# Implications of an $\tilde{O}(n^{1.5})$ 3XORSUM algorithm

(Asked by: username_0 on 2016-12-31)

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](https://cstheory.stackexchange.com/questions/21948/comparing-two-algorithms-for-3sum-problem-over-integers)

**Tags:** cc.complexity-theory, time-complexity

> **Comments:**
> **username_0**: Its a simple, nice target to aim for.  
> **username_1**: 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).  
> **username_0**: @username_1 I'll have a look at those references.  

---

## 0 answers

