This is a survey of pseudorandomness, the theory of efficiently generating objects that" look
random" despite being constructed using little or no randomness. This theory has …

We study the problem of obtaining efficient, deterministic, black-box polynomial identity
testing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and …

This is a survey of unconditional pseudorandom generators (PRGs). A PRG uses a short,
truly random seed to generate a long," pseudorandom" sequence of bits. To be more …

Is randomness ever necessary for space-efficient computation? It is commonly conjectured
that L= BPL, meaning that halting decision algorithms can always be derandomized without …

We propose a new framework for constructing pseudorandom generators for n-variate
Boolean functions. It is based on two new notions. First, we introduce fractional …

The recent line of study on randomness extractors has been a great success, resulting in
exciting new techniques, new connections, and breakthroughs to long standing open …

In this paper, we provide a deterministic ̃O(\logN)-space algorithm for estimating random
walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to …

We present a deterministic O (log log log n)-round low-space Massively Parallel
Computation (MPC) algorithm for the classical problem of (Δ+ 1)-coloring on n-vertex …

We construct pseudorandom generators of seed length Õ (log (n)· log (1/є)) that є-fool
ordered read-once branching programs (ROBPs) of width 3 and length n. For unordered …

A central question in derandomization is whether randomized logspace (RL) equals
deterministic logspace (L). To show that RL= L, it suffices to construct explicit pseudorandom …