Sumegha Garg will present her Pre FPO "Implications of Space-Bounded Computation" on Friday, February 21, 2020 at 10am in CS 402. The members of her committee are as follows: Mark Braverman (advisor); Readers: Mark Braverman and Ran Raz; Examiners: Gillat Kol, Matt Weinberg, and Mark Zhandry. Everyone is invited to her talk. Please see below for the talk abstract. Abstract : The field of complexity theory studies the inherent limits of a computational model for performing certain computational tasks. Most natural is to study restricted computational models that are short of a computational resource, for example, time or memory. While characterizing the minimum time required for a computational task has received more attention, understanding the memory requirements is as fundamental and fascinating, owing to the surprising and non-intuitive results that the field has seen. In my thesis, I focus on understanding the limits of space-bounded computational models and the implications for various algorithmic problems. Implications of bounded space for learning algorithms : [Sha14, SVW16] started the study of feasibility of online learning under memory constraints. In a breakthrough result, [Raz16] showed that learning a n-bit vector from random linear equations requires either Ω(n^2) space or 2^{Ω(n)} samples. My work has focused on extending these memory-sample tradeoffs to a larger class of learning problems and to even when the learner is allowed a second pass over the stream of samples (through an extractor-based approach). Implications of bounded space for randomized algorithms : It is largely unknown if randomization gives space-bounded algorithms 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. In a recent work, a step towards answering this question, we improve upon the previous constructions of hitting sets, which are tools for derandomization. Implications of bounded space for streaming games : In a recent work, we show the impossibility of winning a simple streaming game under memory constraints. In this game, 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 very simple (and memoryless) strategy to avoid losing. We prove that Alice, however, needs at least Ω(N) memory to win.