Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractorsSimulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors

Access Restriction
Subscribed

 Author Barak, B. ♦ Kindler, G. ♦ Shaltiel, R. ♦ Sudakov, B. ♦ Wigderson, A. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2010 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Condensers ♦ Dispersers ♦ Explicit constructions ♦ Extractors ♦ Ramsey graphs Abstract We present new explicit constructions of $\textit{deterministic}$ randomness extractors, dispersers and related objects. We say that a distribution $\textit{X}$ on binary strings of length $\textit{n}$ is a Δ-source if $\textit{X}$ assigns probability at most $2^{™Δn}$ to any string of length $\textit{n}.$ For every Δ>0, we construct the following $poly(\textit{n})-time$ computable functions: 2-source disperser: D:({0, $1}^{n})^{2}$ → {0, 1} such that for any two independent Δ-sources $X_{1},X_{2}$ we have that the support of $D(X_{1},X_{2})$ is {0, 1}. Bipartite Ramsey graph: Let $N=2^{n}.$ A corollary is that the function $\textit{D}$ is a 2-coloring of the edges of $K_{N,N}$ (the complete bipartite graph over two sets of $\textit{N}$ vertices) such that any induced subgraph of size $N^{Δ}$ by $N^{Δ}$ is not monochromatic. 3-source extractor: $\textit{E}:({0,$ $1}^{n})^{3}→$ {0, 1} such that for any three independent Δ-sources $X_{1},X_{2},X_{3}$ we have that $E(X_{1},X_{2},X_{3})$ is $\textit{o}(1)-close$ to being an unbiased random bit. No previous explicit construction was known for either of these for any Δ<1/2, and these results constitute significant progress to long-standing open problems. A component in these results is a new construction of condensers that may be of independent interest: This is a function $\textit{C}:{0,$ $1}^{n}$ → ({0, $1}^{n/c})^{d}$ (where $\textit{c}$ and $\textit{d}$ are constants that depend only on Δ) such that for every Δ-source $\textit{X}$ one of the output blocks of $\textit{C(X)}$ is (exponentially close to) a 0.9-source. (This result was obtained independently by Ran Raz.) The constructions are quite involved and use as building blocks other new and known objects. A recurring theme in these constructions is that objects that were designed to work with independent inputs, sometimes perform well enough with correlated, high entropy inputs. The construction of the disperser is based on a new technique which we call “the challenge-response mechanism” that (in some sense) allows “identifying high entropy regions” in a given pair of sources using only one sample from the two sources. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2010-05-03 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 57 Issue Number 4 Page Count 52 Starting Page 1 Ending Page 52

Open content in new tab

Source: ACM Digital Library