The resolution complexity of the perfect matching principle was studied by Razborov [Raz04], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph $G_n$ such that the resolution complexity of the perfect matching principle for $G_n$ is $2^{\Omega(n)}$, where $n$ is ... more >>>

The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game
initiated a quest for finding \emph{approximate} Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory.

We study the computational complexity of finding an $\eps$-approximate Nash equilibrium with good social ... more >>>

We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On ... more >>>