The Metropolis algorithm is simulated annealing with a fixed temperature.Surprisingly enough, many problems cannot be solved more efficiently by simulated annealing than by the Metropolis algorithm with the best temperature. The problem of finding a natural example (artificial examples are known) where simulated annealing outperforms the Metropolis algorithm for all ... more >>>

We study the complexity of computing $k$-wise independent and
$\epsilon$-biased generators $G : \{0,1\}^n \to \{0,1\}^m$.
Specifically, we refer to the complexity of computing $G$ \emph{explicitly}, i.e.
given $x \in \{0,1\}^n$ and $i \in \{0,1\}^{\log m}$, computing the $i$-th output bit of $G(x)$.
Mansour, Nisan and Tiwari (1990) show that ... more >>>

We revisit the problem of hardness amplification in $\NP$, as
recently studied by O'Donnell (STOC `02). We prove that if $\NP$
has a balanced function $f$ such that any circuit of size $s(n)$
fails to compute $f$ on a $1/\poly(n)$ fraction of inputs, then
$\NP$ has a function $f'$ such ... more >>>