ALMASTY
Algorithms for the Sparse Random 3XOR Problem
Thursday, October 28, 2021Charles Bouillaguet
We present algorithms for variants of the 3XOR problem with lists consisting of random sparse n-bit vectors. We consider two notions of sparsity: low-density (each bit is independently biased towards zero) and low-weight (the Hamming weight of n-bit vectors is fixed). We show that the random sparse 3XOR problem can be solved in strongly subquadratic time, namely less than O(N^{2−epsilon}) operations for a constant epsilon > 0. This stands in strong contrast with the regular case, where it has not been possible to have the exponent drop below 2 − o(1). In the low-density setting, a very simple algorithm even runs in linear time with overwhelming success probability when the density is less than 0.0957. Our algorithms exploit the randomness (and sparsity) of the input in an essential way.
damien.vergnaud (at) nulllip6.fr