Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-034 | 29th March 2007 00:00

An Exposition of Bourgain's 2-Source Extractor

RSS-Feed




TR07-034
Authors: Anup Rao
Publication: 10th April 2007 17:26
Downloads: 1807
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.



ISSN 1433-8092 | Imprint