__
TR07-034 | 29th March 2007 00:00
__

#### An Exposition of Bourgain's 2-Source Extractor

TR07-034
Authors:

Anup Rao
Publication: 10th April 2007 17:26

Downloads: 2962

Keywords:

**Abstract:**
A construction of Bourgain gave the first 2-source

extractor to break the min-entropy rate 1/2 barrier. In this note,

we write an exposition of his result, giving a high level way to view

his extractor construction.

We also include a proof of a generalization of Vazirani's XOR lemma

that seems interesting in its own right, and an argument (due to Boaz

Barak) that shows that any two source extractor with sufficiently

small error must be strong.