Loading...
Please wait, while we are loading the content...
Lecture 13: More Connections with Expanders Based on Scribe Notes
| Content Provider | Semantic Scholar |
|---|---|
| Author | Vadhan, Salil P. Kirsch, Adam Andoni, Alexandr |
| Abstract | Last time we saw the notion of a k →ε k ′ condenser Con : {0, 1}n × {0, 1}d → {0, 1}m, where for every k-source X on {0, 1}n, Con(X,Ud) is ε-close to some k -source. We can define the entropy loss of a condenser to be ` = k − (k + d). As we have discussed, an extractor (i.e. m = k ) must have ` ≥ 2 log(1/ε) − O(1), whereas if we allow m to be larger than k ′ (specifically, m ≥ k + log(1/ε) + O(1)), then it is possible for a condenser to be lossless (i.e. have ` = 0). As we have seen for extractors in Lecture Notes 11, every function Con : {0, 1}n×{0, 1}d → {0, 1}m can be viewed as a bipartite multigraph G with N = 2n left vertices, left-degree D = 2d, and M = 2m right-vertices where the y'th neighbor of left-vertex x is Con(x, y). Generalizing what we showed for extractors, the condenser property implies a vertex-expansion property of the graph G. Specifically, if we define a (= K,A) vertex expander to be one in which sets of size exactly K expand by a factor of A, then we have: |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://people.seas.harvard.edu/~salil/cs225/spring07/lecnotes/lec13.pdf |
| Alternate Webpage(s) | http://www.people.seas.harvard.edu/~salil/cs225/spring07/lecnotes/lec13.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
