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 …

Boolean circuit complexity is the combinatorics of computer science and involves many
intriguing problems that are easy to state and explain, even for the layman. This book is a …

We give an introduction to the area of “randomness extraction” and survey the main
concepts of this area: deterministic extractors, seeded extractors and multiple sources …

We give an explicit construction of an affine extractor (over F_2) that works for affine sources
on n bits with min-entropy k≧\logn⋅(\log\logn)^1+o(1). This improves prior work of Li …

The log-rank conjecture is one of the fundamental open problems in communication
complexity. It speculates that the deterministic communication complexity of any two-party …

We construct explicit subspace-evasive sets. These are subsets of Fn of size| F|(1-ε) n
whose intersection with any k-dimensional subspace is bounded by a constant c (k, ε). This …

In his influential 1947 paper that inaugurated the probabilistic method, Erdős proved the
existence of 2log n-Ramsey graphs on n vertices. Matching Erdős' result with a constructive …

In [1], Dodis and Wichs introduced the notion of a non-malleable extractor. A non-malleable
extractor is a much stronger version of a seeded extractor. Dodis and Wichs showed that …

We prove that any total boolean function of rank r can be computed by a deterministic
communication protocol of complexity O (√ ċ log (r)). Equivalently, any graph whose …

A typical obstacle one faces when constructing pseudorandom objects is undesired
correlations between random variables. Identifying this obstacle and constructing certain …