Description
TitleProjections, extractors, and streaming lower bounds
Date Created2022
Other Date2022-10 (degree)
Extent1 online resource (163 pages) : illustrations
DescriptionIn Part I, we study the theory of randomness extractors in the context of structured sources and their connections with structural results in discrete product spaces. We define a class of sources which are generalizations of somewhere-random sources, which we call manywhere-random sources. We construct both existential and explicit extractors for manywhere-random sources that crucially rely on the structure, and thus perform better than a black-box application of ex- tractors for the corresponding min-entropy of the source. We turn our study to the limits of extraction from manywhere-random sources. We observe that partitioning output domains into multiple parts, and with nice structural properties, is crucial to randomness extraction. Specifically, we show that the existence of a seedless extractor from manywhere-random sources is equivalent to the existence of partitions of output domains with low- dimensional projections of small size. Our output domains here are discrete product spaces, and we hope that our study of projections in these spaces finds other applications in extremal combinatorics, similar to those in randomness extraction we mention here. We use our connection of extraction and structural results on the sizes of projections in partitions of discrete spaces to show limits of randomness extraction from structured sources. This is done by proving lower bounds on the sizes of projections in any partition of the corresponding output space. We show that seedless-extraction is impossible for many different manywhere-random sources over both binary and large alphabets. We turn our focus to the question of extraction in the limiting case of having a large number of sources. Using the connection to projections in product spaces, this problem is equivalent to understanding projections of partitions in high-dimensional product spaces. We thus analyze projection sizes in high dimensions, where we prove that for partitioning into c-parts, the trivial projection size lower bound of 1/c is in fact the best possible, by demonstrating optimal partitions, in the limit of high dimensions. Finally, we show that randomness extraction is possible in manywhere-random sources, in the case when have an astronomical number of “good” - uniform and independent sources, along with a small number of correlated “bad” source. Our result proves that for ϵ → 0⁺ we have an explicit seedless ϵ-extractor for manywhere-random sources, in the limit of the source being extremely long.
In Part II, we study the structure of protocols in communication games that arise from streaming algorithms. We show that space-and-pass-bounded streaming algorithms that solve for a deterministic function of subproblems which are independently drawn from a distribution must approach these subproblems independently. This is proved by showing that we can assume that protocols in novel communication games respect product structure of inputs. Formally, we 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 δ > 0 over random guessing, then it cannot solve XOR of l independent copies of the problem with advantage much better than δˡ/ᵖ. 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+ε)-approximation requires either nΩ(1) space or Ω(1/√ε) passes, even on highly restricted families of graphs such as bounded-degree planar graphs. Our results considerably strengthen prior lower bounds even for arbitrary graphs: starting from the influential work of [Verbin, Yu; SODA 2011], there has been a plethora of lower bounds for single-pass algorithms for these problems; how- ever, the only multi-pass lower bounds proven very recently in [Assadi, Kol, Saxena, Yu; FOCS 2020] rules out sublinear-space algorithms with exponentially smaller o(log (1/ε)) passes for these problems.
NotePh.D.
NoteIncludes bibliographical references
Genretheses
LanguageEnglish
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Statistical Profile