Constantinos Daskalakis Homepage

Short Bio

CSAIL, EECS, MIT
Assistant Professor, Starting July 2009

MICROSOFT RESEARCH, NEW ENGLAND
Post-Doctoral Researcher, 2008-2009

UNIVERSITY OF CALIFORNIA, BERKELEY
Ph.D. in Computer Science, 2004-2008
Microsoft Research Fellowship, 2007-2008
UC Regents Fellowship, 2004-2005
Advisor: Christos H. Papadimitriou
GPA: 4.000/4 (Summa Cum Laude)
Courses: Complexity Theory, Statistical Learning Theory, Reading the Classics, Foundations of Parallel and Distributed Systems, Computational Geometry, Combinatorial Optimization, Randomness and Computation, Pseudorandomness and Extractors, Polynomials of Random Variables, Markov chain Monte Carlo, Great Algorithms, Topics in Probability, Gibbs Measures, Probability Theory, Probability for Applications, Computer Architecture

NATIONAL TECHNICAL UNIVERSITY of ATHENS (NTUA), GREECE
Diploma in Electrical and Computer Engineering, 1999-2004
Thesis: On the Existence of Pure Nash Equilibria in Graphical Games with succinct description
Advisor: Stathis Zachos
GPA: 9.98/10.00 (Summa Cum Laude)

VARVAKIOS HIGH SCHOOL, ATHENS, GREECE
GPA: 20.0/20

Research Interests

My research interests lie in the area of theoretical computer science, in particular algorithmic game theory, computational biology and applied probability.

Recent Publications

Constantinos Daskalakis and Christos H. Papadimitriou, On a Network Generalization of the Minmax Theorem.
In the 36th International Colloquium on Automata, Languages and Programming, ICALP 2009.

Constantinos Daskalakis and Christos H. Papadimitriou, On Oblivious PTAS's for Nash Equilibrium.
In the 41st ACM Symposium On Theory of Computing, STOC 2009.

Sanjeev Arora, Constantinos Daskalakis and David Steurer, Message-Passing Algorithms and Improved LP Decoding.
In the 41st ACM Symposium On Theory of Computing, STOC 2009.

Constantinos Daskalakis, Elchanan Mossel and Sebastien Roch, Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep.
In the 13th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2009.

Kamalika Chaudhuri, Constantinos Daskalakis, Robert Kleinberg and Henry Lin, Online Bipartite Perfect Matching With Augmentation.
In the 28th Conference on Computer Communications, IEEE INFOCOM 2009.

Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant and Paul Valiant, On the Complexity of Nash Equilibria of Action-Graph Games.
In the 20th Annual ACM-SIAM Symposium On Discrete Algorithms, SODA 2009.

Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld and Elad Verbin, Sorting and Ranking in Partially Ordered Sets.
In the 20th Annual ACM-SIAM Symposium On Discrete Algorithms, SODA 2009.

Constantinos Daskalakis, An Efficient PTAS for Two-Strategy Anonymous Games.
In the 4th Workshop on Internet and Network Economics, WINE 2008.

Constantinos Daskalakis and Christos H. Papadimitriou, Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games.
In the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008.

Complete List of Publications

Game Theory

Constantinos Daskalakis and Christos H. Papadimitriou, On a Network Generalization of the Minmax Theorem,
In the 36th International Colloquium on Automata, Languages and Programming, ICALP 2009.
```
@inproceedings{DP:networkminimax,
  title = "On a Network Generalization of the Minmax Theorem",
  author = "Constantinos Daskalakis and Christos H. Papadimitriou",
  year = "2009",
  booktitle = "ICALP",
}
```
[abstract] [bib] [soon in arXiv]

Constantinos Daskalakis and Christos H. Papadimitriou, On Oblivious PTAS's for Nash Equilibrium,
In the 41st ACM Symposium On Theory of Computing, STOC 2009.

If a class of games is known to have a Nash equilibrium with probability values that are either zero or Omega(1)---and thus with support of bounded size---then obviously this equilibrium can be found exhaustively in polynomial time. Somewhat surprisingly, we show that there is a PTAS for the class of games whose equilibria are guaranteed to have small---O(1/n)---values, and therefore large---Omega(n)---supports. We also point out that there is a PTAS for games with sparse payoff matrices, a family for which the exact problem is known to be PPAD-complete [Chen, Deng, Teng 2006]. Both algorithms are of a special kind that we call oblivious: The algorithm just samples a fixed distribution on pairs of mixed strategies, and the game is only used to determine whether the sampled strategies comprise an epsilon-Nash equilibrium; the answer is "yes" with inverse polynomial probability (in the second case, the algorithm is actually deterministic). These results bring about the question: Is there an oblivious PTAS for finding a Nash equilibrium in general games? We answer this question in the negative; our lower bound comes close to the quasi-polynomial upper bound of [Lipton, Markakis, Mehta 2003].

Another recent PTAS for anonymous games [Daskalakis, Papadimitriou 2007 and 2008; Daskalakis 2008] is also oblivious in a weaker sense appropriate for this class of games (it samples from a fixed distribution on unordered collections of mixed strategies), but its running time is exponential in 1/epsilon. We prove that any oblivious PTAS for anonymous games with two strategies and three player types must have 1/epsilon^a in the exponent of the running time for some a >= 1/3, rendering the algorithm in [Daskalakis 2008] (which works with any bounded number of player types) essentially optimal within oblivious algorithms. In contrast, we devise a poly(n)*(1/epsilon)^O(log^2(1/epsilon)) non-oblivious PTAS for anonymous games with two strategies and any bounded number of player types. The key idea of our algorithm is to search not over unordered sets of mixed strategies, but over a carefully crafted set of collections of the first O(log(1/epsilon)) moments of the distribution of the number of players playing strategy 1 at equilibrium. The algorithm works because of a probabilistic result of more general interest that we prove: the total variation distance between two sums of independent indicator random variables decreases exponentially with the number of moments of the two sums that are equal, independent of the number of indicators.
```
@inproceedings{DP:oblivious,
  title = "On Oblivious PTAS's for Nash Equilibrium",
  author = "Constantinos Daskalakis and Christos H. Papadimitriou",
  year = "2009",
  booktitle = "STOC",
}
```
[abstract] [bib] [soon in arXiv]

Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant and Paul Valiant, On the Complexity of Nash Equilibria of Action-Graph Games,
In the 20th Annual ACM-SIAM Symposium On Discrete Algorithms, SODA 2009.

In light of much recent interest in finding a model of multi-player multi-action games that allows for efficient computation of Nash equilibria yet remains as expressive as possible, we investigate the computational complexity of Nash equilibria in the recently proposed model of action-graph games (AGGs). AGGs, introduced by Bhat and Leyton-Brown, are succinct representations of games that encapsulate both local dependencies as in graphical games, and partial indifference to other agents' identities as in anonymous games, which occur in many natural settings such as financial markets. This is achieved by specifying a graph on the set of actions, so that the payoff of an agent for selecting a strategy depends only on the number of agents playing each of the neighboring strategies in the action graph. We present a simple Polynomial Time Approximation Scheme for computing mixed Nash equilibria of AGGs with constant treewidth and a constant number of agent types (but an arbitrary number of strategies). However, the main results of this paper are negative, showing that when either of these conditions is relaxed the problem becomes intractable. In particular, we show that even if the action graph is a tree but the number of agent-types is unconstrained, it is NP-omplete to decide the existence of a pure-strategy Nash equilibrium and PPAD-complete to compute a mixed Nash equilibrium (even an approximate one). Analogously, for AGGs where all agents are of a single type (symmetric AGGs), if the treewidth is unconstrained then deciding the existence of a pure-strategy Nash equilibrium is NP-complete and computing a mixed Nash is PPAD-omplete. These hardness results suggest that, in some sense, our PTAS is as strong a positive result as one can expect. In the broader context of trying to pin down the boundary where the equilibria of multi-player games can be computed efficiently, these results complement recent hardness results for graphical games and algorithmic results for anonymous games.
```
@inproceedings{DSVV:actiongraph08,
  title = "On the Complexity of Nash Equilibria of Action-Graph Games",
  author = "Constantinos Daskalakis and Grant Schoenebeck and Gregory Valiant and Paul Valiant",
  year = "2009",
  booktitle = "SODA",
}
```
[abstract] [bib] [arXiv]

Constantinos Daskalakis, An Efficient PTAS for Two-Strategy Anonymous Games,
In the 4th Workshop on Internet and Network Economics, WINE 2008.

We present a novel polynomial time approximation scheme for two-strategy anonymous games, in which the players' utility functions, although potentially different, do not differentiate among the identities of the other players. Our algorithm computes an epsilon-approximate Nash equilibrium of an n-player 2-strategy anonymous game in time poly(n)*(1/epsilon)^O(1/epsilon^2), which significantly improves upon the running time n^O(1/epsilon^2) required by the algorithm of [Daskalakis, Papadimitriou 2007]. The improved running time is based on a new structural understanding of approximate Nash equilibria: We show that, for any epsilon, there exists an epsilon-approximate Nash equilibrium in which either only O(1/epsilon^3) players randomize, or all players who randomize use the same mixed strategy. To show this result we employ tools from the literature on Stein's Method.
```
@inproceedings{D:anonymous3,
  title = "An Efficient PTAS for Two-Strategy Anonymous Games",
  author = "Constantinos Daskalakis",
  year = "2008",
  booktitle = "WINE",
}
```
[abstract] [bib] [arXiv]

Constantinos Daskalakis and Christos H. Papadimitriou, Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games,
In the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008.

We show that there is a polynomial time approximation scheme for computing Nash equilibria in anonymous games with any fixed number of strategies (a very broad and important class of games), extending the 2-strategy result of Daskalakis and Papadimitriou, 2007. The approximation guarantee follows from a probabilistic result of more general interest: The distribution of the sum of n independent unit vectors with values ranging over {e_1,...,e_k}, where e_i is the unit vector along dimension i of the k-dimensional Euclidean space, can be approximated by the distribution of the sum of another set of independent unit vectors whose probabilities of obtaining each value are multiples of 1/z for some integer z, and so that the variational distance of the two distributions is at most eps, where eps is bounded by an inverse polynomial in z and a function of k, but with no dependence on n. Our probabilistic result specifies the construction of a sparse eps-cover of the space of distributions of sums of independent unit vectors under the total variation distance, which is of interest on its own right.
```
@inproceedings{DP:anonymous08,
  title = "Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games",
  author = "Constantinos Daskalakis and Christos H. Papadimitriou",
  year = "2008",
  booktitle = "FOCS",
}
```
[abstract] [bib] [arXiv]

Constantinos Daskalakis, Alexandros G. Dimakis and Elchanan Mossel, Connectivity and Equilibrium in Random Games,
Submitted, 2008.

We study how the structure of graphical games affects the existence of Nash equilibria. In particular, we are interested to answer whether pure Nash equilibria exist for games played on a given graph; and we study this question over all possible graphical games played on the given graph in the probabilistic sense, by considering the random measure defined by assigning random utility tables to the player-nodes.

We provide conditions for the structure of the graph under which Nash equilibria are likely to exist and complementary conditions which make the existence of Nash equilibria highly unlikely, generalizing known results for games on the complete graph. In particular, we show that bounded degree graphs have Nash equilibria with exponentially small probability in the size of the graph and provide a simple algorithm that finds small non-existence certificates for a large family of graphs. On the contrary, we show that for sufficiently expanding graphs, the number of Nash equilibria is Poisson distributed.

To obtain a refined characterization of how connectivity affects the existence of pure Nash equilibria, we study the question also in the random graph setting. In particular, we look at the case where the interaction graph is drawn from the Erdos-Renyi, G(n, p), model, where each edge is present independently with probability p. For this model we establish a double phase transition for the existence of pure Nash equilibria as a function of the average degree pn, consistent with a non-monotone behavior of the model. We show that when the average degree satisfies np >> (2+Omega(1)) log n, the number of pure Nash equilibria follows a Poisson distribution with parameter 1. When 1/n << np < (0.5 - Omega(1)) log n, pure Nash equilibria fail to exist with high probability. Finally, when np << 1/n a pure Nash equilibrium exists with high probability.
```
@inproceedings{DDM:random games,
  title = "Connectivity and Equilibrium in Random Games",
  author = "Constantinos Daskalakis and Alexandros G. Dimakis and Elchanan Mossel",
  year = "2007",
}
```
[abstract] [bib] [arXiv]

Constantinos Daskalakis and Christos H. Papadimitriou, Computing Equilibria in Anonymous Games,
In the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007.

We present efficient approximation algorithms for finding Nash equilibria in anonymous games, that is, games in which the players utilities, though different, do not differentiate between other players. Our results pertain to such games with many players but few strategies. We show that any such game has an approximate pure Nash equilibrium, computable in polynomial time, with approximation O(s^2 L), where s is the number of strategies and L is the Lipschitz constant of the utilities. Finally, we show that there is a PTAS for finding an eps-approximate Nash equilibrium when the number of strategies is two.
```
@inproceedings{DP:anonymous07,
  title = "Computing Equilibria in Anonymous Games",
  author = "Constantinos Daskalakis and Christos H. Papadimitriou",
  year = "2007",
  booktitle = "FOCS",
}
```
[abstract] [bib] [arXiv]

Constantinos Daskalakis, Aranyak Mehta and Christos H. Papadimitriou, Progress in Approximate Nash Equilibria,
In the 8th ACM Conference on Electronic Commerce, EC 2007.

It is known [Daskalakis, Mehta, Papadimitriou 2006] that an additively eps-approximate Nash equilibrium (with supports of size at most two) can be computed in polynomial time in any 2-player game with eps= .5. It is also known that no approximation better than .5 is possible unless equilibria with support larger than log n are considered, where n is the number of strategies per player. We give a polynomial algorithm for computing an eps-approximate Nash equilibrium in 2-player games with eps= .38; our algorithm computes equilibria with arbitrarily large supports.
```
@inproceedings{DMP:approximate nash 2,
  title = "Progress in Approximate Nash Equilibria",
  author = "Constantinos Daskalakis and Aranyak Mehta and Christos H. Papadimitriou",
  year = "2007",
  booktitle = "EC",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis, Aranyak Mehta and Christos H. Papadimitriou, A Note on Approximate Nash Equilibria,
In the 2nd international Workshop on Internet & Network Economics, WINE 2006. Invited to Theoretical Computer Science Special Issue for WINE 2006.

In view of the intractability of finding a Nash equilibrium, it is important to understand the limits of approximation in this context. A subexponential approximation scheme is known [Lipton, Markakis, Mehta 2003], and no approximation better than 1/4 is possible by any algorithm that examines equilibria involving fewer than log n strategies [Alt94]. We give a simple, linear-time algorithm examining just two strategies per player and resulting in a 1/2 -approximate Nash equilibrium in any 2-player game. For the more demanding notion of well-supported approximate equilibrium due to Daskalakis, Goldberg, Papapdimitriou 2006 no nontrivial bound is known; we show that the problem can be reduced to the case of win-lose games (games with all utilities 0-1), and that an approximation of 5/6 is possible contingent upon a graph-theoretic conjecture.
```
@inproceedings{DMP:approximate nash 1,
  title = "A Note on Approximate Nash Equilibria",
  author = "Constantinos Daskalakis and Aranyak Mehta and Christos H. Papadimitriou",
  year = "2006",
  booktitle = "WINE",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis, Alex Fabrikant and Christos Papadimitriou, The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games,
In the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006.

A recent sequence of results (see below) established that computing Nash equilibria in normal form games is a PPAD-complete problem even in the case of two players. By extending these techniques we prove a general theorem, showing that, for a far more general class of families of succinctly representable multiplayer games, the Nash equilibrium problem can also be reduced to the two-player case. In view of empirically successful algorithms available for this problem, this is in essence a positive result --- even though, due to the complexity of the reductions, it is of no immediate practical significance. We further extend this conclusion to extensive form games and network congestion games, two classes which do not fall into the same succinct representation framework, and for which no positive algorithmic result had been known.
```
@inproceedings{DFP:succinct games,
  title = "The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games",
  author = "Constantinos Daskalakis and Alex Fabrikant and Christos H. Papadimitriou",
  year = "2006",
  booktitle = "ICALP",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis and Christos Papadimitriou, Computing Pure Nash Equilibria via Markov Random Fields,
In the 7th ACM Conference on Electronic Commerce, EC 2006. Best Student Paper Award.

We present a reduction from graphical games to Markov random fields so that pure Nash equilibria in the former can be found by statistical inference on the latter. Our result, when combined with the junction tree algorithm for statistical inference, yields a unified proof of all previously known tractable cases of the NP-complete problem of finding pure Nash equilibria in graphical games, but also implies efficient algorithms for new classes, such as the games with O(log n) treewidth. Furthermore, this important problem becomes susceptible to a wealth of sophisticated and empirically successful techniques from Machine Learning.
```
@inproceedings{DP: nash via MRFs,
  title = "Computing Pure Nash Equilibria via Markov Random Fields",
  author = "Constantinos Daskalakis and Christos H. Papadimitriou",
  year = "2006",
  booktitle = "EC",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis and Christos H. Papadimitriou, Three-Player Games Are Hard,
Manuscript 2005.

We prove that computing a Nash equilibrium in a 3-player game is PPAD-complete, solving a problem left open in our result on the complexity of Nash equilibria.
```
@inproceedings{DP: three players,
  title = "Three-Player Games Are Hard",
  author = "Constantinos Daskalakis and Christos H. Papadimitriou",
  year = "2005",
  booktitle = "ECCC Report",
}
```
[abstract] [bib] [ECCC Report 2005]

Constantinos Daskalakis, Paul W. Goldberg and Christos H. Papadimitriou, The Complexity of Computing a Nash Equilibrium,
In the 38th ACM Symposium on Theory of Computing, STOC 2006. Invited to SIAM Journal on Computing special issue for STOC.

We resolve the question of the complexity of Nash equilibrium by showing that the problem of computing a Nash equilibrium in a game with 4 or more players is complete for the complexity class PPAD. Our proof uses ideas from the recently-established equivalence between polynomial-time solvability of normal-form games and graphical games, and shows that these kinds of games can implement arbitrary members of a PPAD-complete class of Brouwer functions.
```
@inproceedings{DP: complexity of nash equilibria,
  title = "The Complexity of Computing a Nash Equilibrium",
  author = "Constantinos Daskalakis and Paul W. Goldberg and Christos H. Papadimitriou",
  year = "2006",
  booktitle = "STOC",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis and Christos Papadimitriou, The Complexity of Games on Highly Regular Graphs,
In the 13th Annual European Symposium on Algorithms, ESA 2005.

We study the complexity of computing equilibria in succinct games defined on highly regular graphs. Surprisingly, the problem of deciding whether there exists a pure Nash equilibrium in a one-dimensional highly-regular game is NL-complete, whereas if the game is multi-dimensional it is NEXP-complete. Such a dichotomy does not exist for the problem of computing mixed Nash and correlated equilibria. By taking advantage of the regularities of the game we construct a deterministic exponential time algorithm that computes a (succinct description of a) mixed Nash equilibrium of any given highly regular game and a polynomial time algorithm that computes a (succinct description of a) correlated equilibrium.
```
@inproceedings{DP: regular games,
  title = "The Complexity of Games on Highly Regular Graphs",
  author = "Constantinos Daskalakis  and Christos H. Papadimitriou",
  year = "2005",
  booktitle = "ESA",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis, On the Existence of Pure Nash Equilibria in Graphical Games with succinct description,
National Technical University of Athens, 2004 (In Greek).

My diploma thesis at NTUA. My advisor was Stathis Zachos
```
@inproceedings{DP: regular games,
  title = "The Complexity of Games on Highly Regular Graphs",
  author = "Constantinos Daskalakis",
  year = "2005",
  booktitle = "ESA",
}
```
[abstract] [pdf]

Computational Biology

Constantinos Daskalakis, Elchanan Mossel and Sebastien Roch, Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep,
In the 13th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2009.

We introduce a new phylogenetic reconstruction algorithm which, unlike most previous rigorous inference techniques, does not rely on assumptions regarding the branch lengths or the depth of the tree. The algorithm returns a forest which is guaranteed to contain all edges that are: 1) sufficiently long and 2) sufficiently close to the leaves. How much of the true tree is recovered depends on the sequence length provided. The algorithm is distance-based and runs in polynomial time.
```
@inproceedings{DMR:contracted,
  title = "Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep",
  author = "Constantinos Daskalakis and Elchanan Mossel and Sebastien Roch",
  year = "2009",
  booktitle = "RECOMB",
}
```
[abstract] [bib] [soon in arXiv]

Constantinos Daskalakis, Elchanan Mossel and Sebastien Roch, Optimal Phylogenetic Reconstruction,
In the 38th ACM Symposium on Theory of Computing, STOC 2006.

We resolve an important problem in systematic biology, namely that of reconstructing phylogenies from few characters. It is well known that, in order to reconstruct a tree on n taxa, sequences of length at least log n are needed. It was conjectured by Mike Steel that for the Cavender-Farris-Neyman model of evolution, if the mutation probability p on all edges of the tree satisfies 2(1-2p)^2<1, then the tree can be recovered from sequences of length O(log n). We resolve this conjecture in the positive way by describing a phylogenetic reconstruction algorithm that uses O(log n) characters. The algorithm is tight for the Cavender-Farris-Neyman model, since, if the mutation probability does not satisfy 2(1-2p)^2<1, there is a lower bound of polynomially many characters. Finally, our algorithm extends to reconstructing phylogenies from O(log n) taxa in the Jukes-Cantor model and it is tight for the robust reconstruction problem.
```
@inproceedings{DMR: optimal phylo,
  title = "Optimal Phylogenetic Reconstruction",
  author = "Constantinos Daskalakis and Elchanan Mossel and Sebastien Roch",
  year = "2006",
  booktitle = "STOC",
}
```
[abstract] [bib] [arXiv]

C. Daskalakis, C. Hill, A. Jaffe, R. Mihaescu, E. Mossel and S. Rao, Maximal Accurate Forests From Distance Matrices,
In the 10th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2006.

We present a fast converging method for distance-based phylogenetic inference, which is novel in two respects. First, it is the only method (to our knowledge) to guarantee accuracy when knowledge about the model tree, i.e bounds on the edge lengths, is not assumed. Second, our algorithm guarantees that, with high probability, no false assertions are made. The algorithm produces a maximal edge-disjoint subforest of the model tree, with running time O(n^4) in the worst case. Empirical testing has been promising, comparing favorable to Neighbor Joining and Maximum Parsimony, with the advantage of making no false assertions about the topology of the model tree; guarantees against false positives can be controlled as a parameter by the user.
```
@inproceedings{DHJMMR: maximal forests,
  title = "Maximal Accurate Forests From Distance Matrices",
  author = "C. Daskalakis and C. Hill and A. Jaffe and R. Mihaescu and E. Mossel and S. Rao",
  year = "2006",
  booktitle = "RECOMB",
}
```
[abstract] [bib] [pdf]

Applied Probability

Sanjeev Arora, Constantinos Daskalakis and David Steurer, Message-Passing Algorithms and Improved LP Decoding,
In the 41st ACM Symposium On Theory of Computing, STOC 2009.

Linear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance---coming close to that of iterative decoding algorithms---and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman et al. showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis et al. and Koetter and Vontobel.

Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05-fraction of correctable errors for rate-1/2 codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Unlike other techniques, our analysis directly works with the primal linear program and exploits an explicit connection between LP decoding and message passing algorithms.

An interesting byproduct of our method is a notion of a "locally optimal" solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a "re-weighted" version of the min-sum algorithm, obviating the need for linear programming. Our analysis implies, in particular, that this re-weighted version of the min-sum decoder corrects up to a 0.05-fraction of errors.
```
@inproceedings{ADS: Improved LP decoding,
  title = "Message-Passing Algorithms and Improved LP Decoding",
  author = "Sanjeev Arora and Constantinos Daskalakis and David Steurer",
  year = "2009",
  booktitle = "STOC",
}
```
[abstract] [bib] [soon in arXiv]

Constantinos Daskalakis, Alexandros G. Dimakis, Richard Karp and Martin Wainwright, Probabilistic Analysis of Linear Programming Decoding,
In the 18th Annual ACM-SIAM Symposium On Discrete Algorithms, SODA 2007. To appear in IEEE Transactions on Information Theory.

We initiate the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman et al. succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses all prior non-asymptotic results for LDPC codes, and in particular exceeds the best previous finite-length result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a generalized matching. An interesting by-product of our analysis is to establish the existence of "almost expansion" in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, with expansion coefficients much larger than the classical case.
```
@inproceedings{DDKW: LP decoding,
  title = "Probabilistic Analysis of Linear Programming Decoding",
  author = "Constantinos Daskalakis and Alexandros G. Dimakis and Richard Karp and Martin Wainwright",
  year = "2007",
  booktitle = "SODA",
}
```
[abstract] [bib] [arXiv]

Christian Borgs, Jennifer T. Chayes, Constantinos Daskalakis and Sebastien Roch, An Analysis of Preferential Attachment with Fitness,
In the 39th ACM Symposium on Theory of Computing, STOC 2007.

We provide a rigorous analysis of preferential attachment with fitness, suggested by Bianconi and Barabasi and studied by Motwani and Xu, in which the degree of a vertex is scaled by its quality to determine its attractiveness. Including quality considerations in the classical preferential attachment model provides a much more realistic description of many complex networks, such as the web graph, and allows to observe a much richer behavior in the growth dynamics of these networks. Specifically, depending on the shape of the distribution from which the qualities of the vertices are drawn, we observe three distinct phases, namely a first-mover-advantage phase, a fit-get-richer phase and an innovation-pays-off phase. We precisely characterize the properties of the quality distribution that result in each of these phases and we compute the exact growth dynamics for each phase. The dynamics provide rich information about the quality of the vertices, which can be very useful in many practical contexts, including ranking algorithms for the web, recommendation algorithms, as well as the study of social networks.
```
@inproceedings{BCDR: pref attachment fitness,
  title = "An Analysis of Preferential Attachment with Fitness",
  author = "Christian Borgs and Jennifer T. Chayes and Constantinos Daskalakis and Sebastien Roch",
  year = "2007",
  booktitle = "STOC",
}
```
[abstract] [bib] [pdf]

Other

Kamalika Chaudhuri, Constantinos Daskalakis, Robert Kleinberg and Henry Lin, Online Bipartite Perfect Matching With Augmentation,
In the 28th Conference on Computer Communications, IEEE INFOCOM 2009.

In this paper, we study an online bipartite matching problem, motivated by applications in wireless communication, content delivery, and job scheduling. In our problem, we have a bipartite graph G between n clients and n servers, which represents the servers to which each client can connect. Although the edges of G are unknown at the start, we learn the graph over time, as each client arrives and requests to be matched to a server. As each client arrives, she reveals the servers to which she can connect, and the goal of the algorithm is to maintain a matching between the clients who have arrived and the servers. Assuming that G has a perfect matching which allows all clients to be matched to servers, the goal of the online algorithm is to minimize the switching cost, the total number of times a client needs to switch servers in order to maintain a matching at all times.

Although there are no known algorithms which are guaranteed to yield switching cost better than the trivial O(n^2) in the worst case, we show that the switching cost can be much lower in three natural settings. In our first result, we show that for any arbitrary graph G with a perfect matching, if the clients arrive in random order, then the total switching cost is only O(n log n) with high probability. This bound is tight, as we show an example where the switching cost is Omega(n log n) in expectation. In our second result, we show that if each client has edges to Theta(log n) uniformly random servers, then the total switching cost is even better; in this case, it is only O(n) with high probability, and we also have a lower bound of Omega(n/log n). In terms of the number of edges needed for each client, our result is tight, since Omega(log n) edges are needed to guarantee a perfect matching in G with high probability. In our last result, we derive the first algorithm known to yield total cost O(n log n), given that the underlying graph G is a forest. This is the first result known to match the existing lower bound for forests, which shows that any online algorithm must have switching cost Omega(n log n), even when G is restricted to be a forest.
```
@inproceedings{CSKL: onlineMatching,
  title = "Online Bipartite Perfect Matching With Augmentation",
  author = "Kamalika Chaudhuri and Constantinos Daskalakis and Robert Kleinberg and Henry Lin",
  year = "2009",
  booktitle = "IEEE INFOCOM",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld and Elad Verbin, Sorting and Ranking in Partially Ordered Sets,
In the 20th Annual ACM-SIAM Symposium On Discrete Algorithms, SODA 2009.

Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study these problems in the context of partially ordered sets, in which some pairs of objects are incomparable. This generalization is interesting from a combinatorial perspective, and it has immediate applications in ranking scenarios where there is no underlying linear ordering, e.g., conference submissions. It also has applications in reconstructing certain types of networks, including biological networks.

Our results represent significant progress over previous results from two decades ago by Faigle and Turan. In particular, we present the first algorithm that sorts a width-w poset of size n with optimal query complexity O(n (w + log n)). We also describe a variant of Mergesort with query complexity O(w n log(n/w)) and total complexity O(w^2 n log(n/w); an algorithm with the same query complexity was given by Faigle and Turan, but no efficient implementation of that algorithm is known. Both our sorting algorithms can be applied with negligible overhead to the more general problem of reconstructing transitive relations.

We also consider two related problems: finding the minimal elements, and its generalization to finding the bottom k "levels", called the k-selection problem. We give efficient deterministic and randomized algorithms for finding the minimal elements with O(w n) query and total complexity. We provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k-selection problem. Finally, we present efficient algorithms for computing a linear extension of a poset and computing the heights of all elements.
```
@inproceedings{DKMRV: sorting posets,
  title = "Sorting and Ranking in Partially Ordered Sets",
  author = "Constantinos Daskalakis and Richard M. Karp and Elchanan Mossel and Samantha Riesenfeld and Elad Verbin ",
  year = "2009",
  booktitle = "SODA",
}
```
[abstract] [bib] [arxiv]

Stergios Stergiou, Constantinos Daskalakis and George K. Papakonstantinou, Fast and Efficient Heuristic ESOP Minimization Algorithm,
IEEE Great Lakes Symposium on VLSI (GLSVLSI 2004).

We present an algorithm that solves a fundamental theoretical problem in logic synthesis, the problem of Exclusive-Sum-of-Products Minimization. Our algorithm is compared to the state-of-the art algorithm used in most CAD-programs. The experiments show that our algorithm matches and in some cases surpasses the performance of the state of the art algorithm.
```
@inproceedings{SDP: esop minimization,
  title = "Fast and Efficient Heuristic ESOP Minimization Algorithm",
  author = "Stergios Stergiou and Constantinos Daskalakis and George K. Papakonstantinou",
  year = "2004",
  booktitle = "GLSVLSI",
}
```
[abstract] [bib] [pdf]

Awards

Here is a list of some awards for which my parents are proud:).