An algorithm is presented for counting the number of maximum weight satisfying assignments of a 2SAT formula. The worst case running time of $O(\mbox{poly($n$)} \cdot 1.2461^n)$ for formulas with $n$ variables improves on the previous bound of $O(\mbox{poly($n$)} \cdot 1.2561^n)$ by Dahll\"of, Jonsson, and Wahlstr\"om . The weighted 2SAT counting ... more >>>

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 $$\frac{2^n}{n}(1+\frac{\log
n}{n}-O(\frac{1}{n})) \leq L(n) \leq\frac{2^n}{n}(1+3\frac{\log
n}{n}+O(\frac{1}{n}))$$ 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 >>>