Skip navigation
Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorBraverman, Mark-
dc.contributor.authorGarg, Sumegha-
dc.contributor.otherComputer Science Department-
dc.description.abstractThe field of computational complexity theory studies the inherent difficulties of performing certain computational tasks with limited resources. While characterizing the minimum time required for a computational task has received more attention, understanding the memory requirements is as fundamental and fascinating. The focus of this thesis is understanding the limits of space-bounded computation and implications for various algorithmic problems. 1. Implications of bounded space for learning algorithms: [SVW16] and [Sha14] started the study of online learning under memory constraints. In a breakthrough result, [Raz16] showed that learning an unknown n-bit vector from random linear equations (in F_2) requires either Ω(n^2) space (memory) or 2^Ω(n) samples. Work in this thesis extends these memory-sample tradeoffs to a larger class of learning problems through an extractor-based approach, to when the learner is allowed a second pass over the stream of samples and, to proving security of Goldreich’s local pseudorandom generator against memory-bounded adversaries in the streaming model. 2. Implications of bounded space for randomized algorithms: It is largely unknown if randomization gives space-bounded computation any advantage over deterministic computation. The current best hope of the community is to derandomize randomized log-space computation with one-sided error, that is, prove RL = L. A work presented in this thesis, in a step towards answering this question, improved upon the state-of-the-art constructions of hitting sets, which are tools for derandomization. 3. Implications of bounded space for mirror games: In this thesis, we show the impossibility of winning the following streaming game under memory constraints. Alice and Bob take turns saying numbers belonging to the set {1, 2, ..., 2N}. A player loses if they repeat a number that has already been said. Bob, who goes second, has a memory-less strategy to avoid losing. Alice, however, needs at least Ω(N) memory to not lose.-
dc.publisherPrinceton, NJ : Princeton University-
dc.relation.isformatofThe Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: <a href=> </a>-
dc.subjectBranching Programs-
dc.subjectMirror Games-
dc.subjectOnline Learning-
dc.subjectSpace Complexity-
dc.subjectTime-Space Tradeoffs-
dc.subject.classificationComputer science-
dc.titleImplications of Space-Bounded Computation-
dc.typeAcademic dissertations (Ph.D.)-
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Garg_princeton_0181D_13417.pdf1.14 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.