Hardcore Bits

(... to be written)

Sources

Hardcore bits are being discussed in [FOC, Volume 1, Chapter 2.5 Hardcore Predicates]. They are also discussed in [KL15, Chapter 7]. The Goldreich-Levin theorem[GL89] is discussed in [FOC, Volume 1, Section 2.5.2] and fully reproduced in [G01]. The Blum-Micali '82 construction is from [BM82].

Vinod Vaikuntanathan gave a two parts lecture on hardcore bits in "L4: Hardcore Bits" of an advanced course. The part about hardcore bits starts at 43:35, and the Blum-Micali '82 theorem w/ reduction proof starts at 51:53. You may still want to watch the whole lecture from the beginning, as it also covers random self-reducibility and coin tossing over the phone:

The Goldreich-Levin theorem is shown and proved in "L5: Hardcore Bits From One-way Functions":

Literature