Sumegha Garg will present her FPO "Implications of Space-Bounded Computation" on June 12, 2020 at 10:30am via Zoom. Zoom link: [ https://princeton.zoom.us/j/93 | https://princeton.zoom.us/j/93 ] The members of her committee are as follows: Examiners: Mark Zhandry, Gillat Kol, and Matt Weinberg; Readers: Mark Braverman (adviser) and Ran Raz. A copy of her thesis, is available upon request. Please email ngotsis@cs.princeton if you would like a copy of the thesis. Everyone is invited to attend her talk. The 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 F2) requires either Ω(n2) 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.