|
for any subset A of N of size at least K, choosing a random node in A and then following a random edge brings you to a node x on the right side with probability within e of 1/M. These graphs are called "extractors" because they can be used to "extract" randomness from weak random sources. Here are some other uses of extractors: Random sampling using few random bits Simulating randomized algorithms using weak random sources Expanders that beat the eigenvalue bound Error-correcting codes with good list decoding properties. |
|
for any subset A of N of size at least K, choosing a random node in A and then following a random edge brings you to a node x on the right side with probability within e of the uniform distribution. |
|
These graphs are called "extractors" because they can be used to "extract" randomness from weak random sources. |
![[Home]](wikipedia.png)