Title:           Proving Hard-Core Predicates Using List Decoding
Speaker:         Adi Akavia, MIT
Joint work with: Shafi Goldwasser and Muli Safra
Abstract:

We introduce a unifying framework for proving that predicate P is
hard-core for a one-way function f, and apply it to a broad family of
functions and predicates, reproving old results in an entirely
different way as well as showing new hard-core predicates for well
known one-way function candidates.

Our framework extends the list-decoding method of Goldreich and Levin
for showing hard-core predicates. Namely, a predicate will correspond
to some error correcting code, predicting a predicate will correspond
to access to a corrupted codeword, and the task of inverting one-way
functions will correspond to the task of list decoding a corrupted
codeword.

A characteristic of the error correcting codes which emerge and are
addressed by our framework, is that codewords can be approximated by a
small number of heavy coefficients in their Fourier
representation. Moreover, as long as corrupted words are close enough
to legal codewords, they will share a heavy Fourier coefficient. We
list decode such codes, by devising a learning algorithm applied to
corrupted codewords for learning heavy Fourier coefficients.