We study the problem of constructing explicit extractors for independent general weak random sources. Given weak sources on $n$ bits, the probabilistic method shows that there exists a deterministic extractor for two independent sources with min-entropy as small as $\log n+O(1)$. However, even to extract from a constant number of ... more >>>

We consider the problem of compression for ``easy'' Boolean functions: given the truth table of an $n$-variate Boolean function $f$ computable by some \emph{unknown small circuit} from a \emph{known class} of circuits, find in deterministic time $\poly(2^n)$ a circuit $C$ (no restriction on the type of $C$) computing $f$ so ... more >>>

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial
that approximates $f$ within $1/3$ at every point. We prove that the function $\bigwedge_{i=1}^{n}\bigvee_{j=1}^{n}x_{ij}$,
known as the AND-OR tree, has approximate degree $\Omega(n).$ This lower bound is tight
and closes a ... more >>>