In this paper we review the known bounds for L(n), the circuit size
complexity of the hardest Boolean function on n input bits. The
best known bounds appear to be

However, the bounds do not seem to be
explicitly stated in the literature. We ... more >>>

We study the computational complexity of deciding the existence of a
Pure Nash Equilibrium in multi-player strategic games.
We address two fundamental questions: how can we represent a game?, and
how can we represent a game with polynomial pay-off functions?
Our results show that the computational complexity of
deciding ... more >>>

We give a randomized algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its running time is at most 2^{n(1-1/\alpha)} up to a polynomial factor, where \alpha = \ln(m/n) + O(\ln \ln m) and n, m are respectively the number of variables ... more >>>