We give an explicit construction of depth two threshold circuit with polynomial weights and $\tilde{O}(n^5)$ gates that computes an arbitrary threshold function. We also give the construction of such circuits with $O(n^3/\log n)$ gates computing the COMPARISON and CARRY functions, and that with $O(n^4/\log n)$ gates computing the ADDITION function. ... more >>>

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 >>>