In this work we study two seemingly unrelated notions. Locally Decodable Codes(LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing ... more >>>

We exhibit an explicitly computable `pseudorandom' generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same ... more >>>

We show that RL is contained in L/O(n), i.e., any language computable
in randomized logarithmic space can be computed in deterministic
logarithmic space with a linear amount of non-uniform advice. To
prove our result we show how to take an ultra-low space walk on
the Gabber-Galil expander graph.

more >>>