[ TGIF talk abstract ]

"Hard-Core Bits, the Goldreich-Levin Theorem, and Local List Decoding"
David Molnar
09/12/2003

My talk will give an overview of "hard core bits," the Goldreich-Levin
proof of their existence, and connections to "local list decoding." First,
I'll define a one-way function as a function f such that f(x) is easy to
compute, but it is hard to find any element of f^-1(x). Then I'll show
that there exist one-way functions that meet a natural definition of
"one-way"ness but nevertheless "leak" information about individual bits of
their input. In an attempt to remedy the situation, I'll define the notion
of a "hard-core bit" and argue that it captures a natural notion of
"distilling" the hardness of a one-way function.

Surprisingly, it turns out that a hard-core bit exists for *any* one-way
function. This result is the Goldreich-Levin Theorem, which is of
foundational importance in cryptography. Theorists outside cryptography,
however, care about the theorem because its proof gave the first known
practical algorithm for "local list decoding" of any code.

I will talk about this notion of "local list decoding," explain its
importance, and explore the connections between the Goldreich-Levin
hard-core bit and the Hadamard Code. Finally, if there's any time left, I
will end by superbrief summarizing a result of Adcock and Cleve that shows
a quantum version of the Goldreich-Levin theorem and speculating about
quantum algorithms for local list decoding.