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 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 >>>

We consider the well known problem of determining the k'th vertex reached by chasing pointers in a directed graph of out-degree 1. The famous "pointer doubling" technique provides an O(log k) parallel time algorithm on a Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that this problem requires Omega(k) steps on an ... more >>>

more >>>

We show how to construct length-preserving 1-1 one-way functions based on popular intractability assumptions (e.g., RSA, DLP). Such 1-1 functions should not be confused with (infinite) families of (finite) one-way permutations. What we want and obtain is a single (infinite) 1-1 one-way function. more >>>

We present a Logspace, many-one reduction from the undirected st-connectivity problem to its complement. This shows that $SL=co-SL$ more >>>

This paper concerns the open problem of Lovasz and Saks regarding the relationship between the communication complexity of a boolean function and the rank of the associated matrix. We first give an example exhibiting the largest gap known. We then prove two related theorems. more >>>