Abstract
We study the problem of extracting randomness from somewhererandom sources, and related combinatorial phenomena: partition analogues of Shearer’s lemma on projections.
A somewhererandom source is a tuple (X_1, …, X_t) of (possibly correlated) {0,1}ⁿ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 somewhererandom source as input and outputs nearly uniform random bits. We study the seedlength needed for extracting mergers with constant t and constant error.
Since a somewhererandom source has minentropy at least n, a standard extractor can also serve as an extracting merger. Our goal is to understand whether the further structure of being somewhererandom rather than just having high entropy enables smaller seedlength, and towards this 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 secondmoment strengthening of the graphtheoretic approach of Radhakrishnan and TaShma to extractors.
All this is in contrast to the status for condensing mergers (where the output is only required to have high minentropy), whose seedlength/outputlength tradeoffs can all 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 3dimensional cube [0,1]³ into two parts, one of the parts has an axis parallel 2dimensional projection of area at least 3/4.
BibTeX  Entry
@InProceedings{kopparty_et_al:LIPIcs.APPROX/RANDOM.2023.52,
author = {Kopparty, Swastik and N, Vishvajeet},
title = {{Extracting Mergers and Projections of Partitions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {52:152:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772969},
ISSN = {18688969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18877},
URN = {urn:nbn:de:0030drops188777},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.52},
annote = {Keywords: randomness extractors, randomness mergers, extracting mergers, partitions, projections of partitions, covers, projections of covers}
}
Keywords: 

randomness extractors, randomness mergers, extracting mergers, partitions, projections of partitions, covers, projections of covers 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) 
Issue Date: 

2023 
Date of publication: 

04.09.2023 