The symmetric binary perceptron (\mathrm{SBP}_{\kappa}) problem with parameter \kappa : \mathbb{R}_{\geq1} \to [0,1] is an average-case search problem defined as follows: given a random Gaussian matrix \mathbf{A} \sim \mathcal{N}(0,1)^{n \times m} as input where m \geq n, output a vector \mathbf{x} \in \{-1,1\}^m such that $$|| \mathbf{A} \mathbf{x} ||_{\infty} \leq ... more >>>

We show that for all functions t(n) \geq n, every multitape Turing machine running in time t can be simulated in space only O(\sqrt{t \log t}). This is a substantial improvement over Hopcroft, Paul, and Valiant's simulation of time t in O(t/\log t) space from 50 years ago [FOCS 1975, ... more >>>

We present a new technique for using catalytic space to simulate space-bounded randomized algorithms.
Allocate one bit on the catalytic tape for each configuration of a randomized machine.
Simulate the machine several times.
Each time it requests a random bit, use the bit from the catalytic tape corresponding to its ... more >>>