Access Restriction

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

   Open content in new tab
Source: ACM Digital Library