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

A distribution X over binary strings of length n has min-entropy k if every string has probability at most 2 - k in X . We say that X is a δ-source if its rate k ⁄ n is at least δ.We give the following new explicit instructions (namely, poly(n)- time computable functions) of deterministic extractors, dispersers and related objects. All work for any fixed rate δ>0. No previous explicit construction was known for either of these, for any δ‹1⁄2. The first two constitute major progress to very long-standing open problems. Bipartite Ramsey f 1 : (0,1) n ) 2 →0,1, such that for any two independent δ-sources X 1 , X 2 we have f 1 ( X 1 , X 2 ) = 0,1 This implies a new explicit construction of 2N -vertex bipartite graphs where no induced N δ by N δ subgraph is complete or empty. Multiple source extraction f 2 : (0,1 n ) 3 →0,1 such that for any three independent δ-sources X 1 , X 2 , X 3 we have that f 2 ( X 1 , X 2 , X 3 ) is ( o (1)-close to being) an unbiased random bit. Constant seed condenser 2 f 3 : n →(0,1 m ) c , such that for any δ-source X , one of the c output distributions f 3 ( X ) i , is a 0.9-source over 0,1 m . Here c is a constant depending only on δ. Subspace Ramsey f 4: 0,1 n →0,1 such that for any affine -δ-source 3 X we have f 4 ( X )= 0,1.

Authors

• Boaz Barak
• Guy Kindler
• Ronen Shaltiel
• Benny Sudakov
• Avi Wigderson

Keywords

• constructions
• dispersers condenser
• explicit
• extractors
• ramsey graphs