CS Events

Abstract:

In Part I, we study randomness extractors.

We define a class of structured sources closely related to somewhere-random sources, which we call somewhere-bad sources. We show that the existence of a seedless extractor from somewhere- sources is equivalent to the existence of partitions of output domains with low-dimensional projections of small size. We prove bounds on projection sizes for partitioning into multiple parts, and also in the case of high dimensions. Some of our bounds are optimal for many different parts and many different projections. Our projection size results stand independently of randomness extraction, and we hope will find applications elsewhere.

Finally, inspired by our lower bounds for seedless-extraction, we construct both existential and explicit seeded extractors for somewhere-random and somewhere-bad sources that crucially rely on the structure, and performs better than using a standard extractor that simply ignores source structure, for any output length smaller than the order of the full min-entropy of the source.

In Part II, we study space-pass tradeoff for multi-pass streaming algorithms. 

W prove a simple streaming XOR Lemma, a generic hardness amplification result: which says that, if a p-pass s-space streaming algorithm can only solve a decision problem with advantage $delta >0$ over random guessing, then it cannot solve XOR of $ell$ independent copies of the problem with advantage much better than $delta^{ell/p}$. This result can be of independent interest and useful for other streaming lower bounds as well.

We use our streaming XOR lemma to show space-pass tradeoffs in graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and maximum cuts, weight of minimum spanning trees, or testing if a graph is connected or cycle-free versus being far from these properties. We develop a new lower bound technique that proves that for many problems of interest, including all the above, obtaining a $(1+eps)$-approximation requires either $n^(Omega(1))$-space or $Omega(1/ sqrt(eps))$ passes, even on highly restricted families of graphs such as bounded-degree planar graphs.