ECCC-Report TR07-034https://eccc.weizmann.ac.il/report/2007/034Comments and Revisions published for TR07-034en-usTue, 10 Apr 2007 17:26:45 +0300
Paper TR07-034
| An Exposition of Bourgain's 2-Source Extractor |
Anup Rao
https://eccc.weizmann.ac.il/report/2007/034A 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.
Tue, 10 Apr 2007 17:26:45 +0300https://eccc.weizmann.ac.il/report/2007/034