A Subquadratic Algorithm for 3XOR

Martin Dietzfelbinger, Philipp Schlag, Stefan Walzer

Given a set $X$ of $n$ binary words of equal length $w$, the 3XOR problem asks for three elements $a,b,c\in X$ such that $a\oplus b=c$, where $\oplus$ denotes the bitwise XOR…