The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem (Extended Abstract)
Vadim Lyubashevsky · 2005
In (2), Blum et al. demonstrated the first sub-exponential algorithm for learning the parity function in the presence of noise. They solved the length-n parity problem in time 2 O(n/ log n) but it required the availability of 2 O(n/ log n) labeled examples. As an open problem, they asked whether there exists a 2 o(n) algorithm for the length-n parity problem that uses only poly(n) labeled examples. In this work, we provide a positive answer to this question. We show that there is an algorithm that solves the length-n parity problem in time 2 O(n/ log log n) using n 1+� labeled examples. This result immediately gives us a sub-exponential algorithm for decoding n × n 1+� random binary linear codes (i.e. codes where the messages are n bits and the codewords are n 1+� bits) in the presence of random noise. We are also able to extend the same techniques to provide a sub-exponential algorithm for dense instances of the random subset sum problem.