We focus on the problem of computing an $\epsilon$-Nash equilibrium of a bimatrix game, when $\epsilon$ is an absolute constant.
We present a simple algorithm for computing a $\frac{3}{4}$-Nash equilibrium for any bimatrix game in strongly polynomial time and
we next show how to extend this algorithm so as to ... more >>>

A dimension extractor is an algorithm designed to increase the effective dimension -- i.e., the computational information density -- of an infinite sequence. A constructive dimension extractor is exhibited by showing that every sequence of positive constructive dimension is Turing equivalent to a sequence of constructive strong dimension arbitrarily ... more >>>

We prove that any AC0 circuit augmented with {epsilon log^2 n}
MOD_m gates and with a MAJORITY gate at the output, require size
n^{Omega(log n)} to compute MOD_l, when l has a prime
factor not dividing m and epsilon is sufficiently small. We
also obtain ... more >>>