We present a very simple reduction that when given a graph G and an integer k produces a game that has an evolutionary stable strategy if and only if the maximum clique size of G is not exactly k. Formally this shows that existence of evolutionary stable strategies is hard ... more >>>

We show that every language in NP has a *statistical* zero-knowledge
argument system under the (minimal) complexity assumption that
one-way functions exist. In such protocols, even a computationally
unbounded verifier cannot learn anything other than the fact that the
assertion being proven is true, whereas a polynomial-time prover
cannot convince ... more >>>

We consider computationally-efficient incentive-compatible
mechanisms that use the VCG payment scheme, and study how well they
can approximate the social welfare in auction settings. We obtain a
$2$-approximation for multi-unit auctions, and show that this is
best possible, even though from a purely computational perspective
an FPTAS exists. For combinatorial ... more >>>