Wei Zhan will present his General Exam "Time-space tradeoff for memory game and random input model"on Monday, May 20, 2019 at 1pm in CS 401. BQ_BEGIN The members of his committee are as follows: Ran Raz (adviser), Gillat Kol, and Mark Braverman. BQ_END BQ_BEGIN Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. BQ_END BQ_BEGIN Abstract: In many natural problems, one can trade space for time by saving intermediate results, or vice versa by recomputing them. We examine this time-space tradeoff phenomenon in the following two specific problems: Memory game. The objective is to match n pairs of cards where you can only reveal one at a time. We resolve the two open questions left in [Chakrabarti & Chen, 2017] and obtain the tight time-spaces tradeoffs for the memory game: TS=Θ(n^2) in equality query model, and T^2S=Θ(n^3) for general randomized branching programs. Parity in random input model. We purpose this new model where in every step a uniformly random index is given, along with the input bit at this index. If some restricted dependencies are allowed among the inputs, any lower bound under this model will give a lower bound for oblivious branching programs. We show a tight TS=Θ(n^2) bound for computing pairty under this model with a special type of branching programs. Reading List: Textbook: Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach Papers: Paul Beame, Michael Saks, Xiaodong Sun, and Erik Vee. Time-space tradeoff lower bounds for randomized computation of decision problems. László Babai, Noam Nisan and Márió Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs Ran Raz. Fast learning requires good memory: A time-space lower bound for parity learning Sumegha Garg, Ran Raz and Avishay Tal. Extractor-Based Time-Space Lower Bounds for Learning Allan Borodin and Stephen A. Cook. A time-space tradeoff for sorting on a general sequential model of computation P. Beame, R. Clifford, and W. Machmouchi. Element Distinctness, Frequency Moments, and Sliding Windows Amit Chakrabarti, Yining Chen. Time-Space Tradeoffs for the Memory Game Lance Fortnow. Time-Space Tradeoffs for Satisfiability Dylan McKay and Ryan Williams. Quadratic Time-Space Lower Bounds for Computing Natural Functions With a Random Oracle BQ_END