Algorithmic meta-theorems are general algorithmic results applying to a whole range of problems, rather than just to a single problem alone. They often have a logical and a
structural component, that is they are results of the form:
"every computational problem that can be formalised in a given logic L ... more >>>

We show that if Arthur-Merlin protocols can be derandomized, then there is a Boolean function computable in deterministic exponential-time with access to an NP oracle, that cannot be computed by Boolean circuits of exponential size. More formally, if $\mathrm{prAM}\subseteq \mathrm{P}^{\mathrm{NP}}$ then there is a Boolean function in $\mathrm{E}^{\mathrm{NP}}$ that requires ... more >>>

We study the complexity of {\em rationalizing} network formation. In
this problem we fix an underlying model describing how selfish
parties (the vertices) produce a graph by making individual
decisions to form or not form incident edges. The model is equipped
with a notion of stability (or equilibrium), and we ... more >>>