Extracting Mergers and Projections of Partitions
share
We study the problem of extracting randomness from somewhere-random sources, and related combinatorial phenomena: partition analogues of Shearer's lemma on projections. A somewhere-random source is a tuple (X_1, …, X_t) of (possibly correlated) {0,1}^n-valued random variables X_i where for some unknown i ∈ [t], X_i is guaranteed to be uniformly distributed. An extracting merger is a seeded device that takes a somewhere-random source as input and outputs nearly uniform random bits. We study the seed-length needed for extracting mergers with constant t and constant error. We show: · Just like in the case of standard extractors, seedless extracting mergers with even just one output bit do not exist. · Unlike the case of standard extractors, it is possible to have extracting mergers that output a constant number of bits using only constant seed. Furthermore, a random choice of merger does not work for this purpose! · Nevertheless, just like in the case of standard extractors, an extracting merger which gets most of the entropy out (namely, having Ω (n) output bits) must have Ω (log n) seed. This is the main technical result of our work, and is proved by a second-moment strengthening of the graph-theoretic approach of Radhakrishnan and Ta-Shma to extractors. In contrast, seed-length/output-length tradeoffs for condensing mergers (where the output is only required to have high min-entropy), can be fully explained by using standard condensers. Inspired by such considerations, we also formulate a new and basic class of problems in combinatorics: partition analogues of Shearer's lemma. We show basic results in this direction; in particular, we prove that in any partition of the 3-dimensional cube [0,1]^3 into two parts, one of the parts has an axis parallel 2-dimensional projection of area at least 3/4.
READ FULL TEXT