We give new pseudorandom generators for \emph{regular} read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is (0 or) $2$. For every width $d$ and length $n$, our pseudorandom generator uses a seed of length $O((\log d + \log\log n ... more >>>

Does computing n copies of a function require n times the computational effort? In this work, we give the first non-trivial answer to this question for the model of randomized communication complexity. We show that: 1. Computing n copies of a function requires sqrt{n} times the communication. 2. For average ... more >>>

We give polynomial time computable extractors for low-weight affine sources. A distribution is affine if it samples a random point from some unknown low dimensional subspace of F^n_2 . A distribution is low weight affine if the corresponding linear space has a basis of low-weight vectors. Low-weight ane sources are ... more >>>

In a two player game, a referee asks two cooperating players (who are not allowed to communicate) questions sampled from some distribution and decides whether they win or not based on some predicate of the questions and their answers. The parallel repetition of the game is the game in which ... more >>>

A construction of Bourgain gave the first 2-source extractor to break the min-entropy rate 1/2 barrier. In this note, we write an exposition of his result, giving a high level way to view his extractor construction. We also include a proof of a generalization of Vazirani's XOR lemma that seems ... more >>>

We consider the problem of bit extraction from independent sources. We construct an extractor that can extract from a constant number of independent sources of length $n$, each of which have min-entropy $n^\gamma$ for an arbitrarily small constant $\gamma > 0$. Our constructions are different from recent extractor constructions \cite{BarakIW04, ... more >>>