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.
Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach
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