Short Bio
CSAIL, EECS, MIT
XWindow Consortium Associate Professor, 2012  present
XWindow Consortium Assistant Professor, 2011  2012
Assistant Professor, 2009  2011
MICROSOFT RESEARCH, NEW ENGLAND
PostDoctoral Researcher, 20082009
UNIVERSITY OF CALIFORNIA, BERKELEY
Ph.D. in Computer Science, 20042008
2008 ACM Doctoral Dissertation Award
2007 Microsoft Research Fellowship
2004 UC Regents Fellowship
Advisor: Christos H. Papadimitriou
NATIONAL TECHNICAL UNIVERSITY of ATHENS (NTUA), GREECE
Diploma in Electrical and Computer Engineering, 19992004
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)
Research Interests
My research interests lie in the area of theoretical computer science, in particular algorithmic game theory, computational biology and applied probability.
Awards
Here is a list of
awards.
Journal Articles

Constantinos Daskalakis, Alan Deckelbaum and Anthony Kim: NearOptimal NoRegret Algorithms for Zerosum Games.
To appear in Games and Economic Behavior. Special Issue for STOC/FOCS/SODA 2011. Invited. pdf

Constantinos Daskalakis: On the Complexity of Approximating a Nash Equilibrium.
ACM Transactions on Algorithms (TALG), 9(3): 23, 2013. Special Issue for SODA 2011. Invited. pdf

Constantinos Daskalakis and Sebastien Roch: AlignmentFree Phylogenetic Reconstruction: Sample Complexity via a Branching Process Analysis.
Annals of Applied Probability, 23(2): 693721, 2013. arxiv
 Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim and Sebastien Roch: Global Alignment of Molecular Sequences via Ancestral State Reconstruction.
Stochastic Processes and their Applications, 122(12): 38523874, 2012. pdf

Sanjeev Arora, Constantinos Daskalakis and David Steurer: MessagePassing Algorithms and Improved LP Decoding.
IEEE Transactions on Information Theory, 58(12): 72607271, 2012.
 Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld and Elad Verbin: Sorting and Selection in Posets.
SIAM Journal on Computing, 40(3): 597622, 2011. arxiv
 Constantinos Daskalakis, Elchanan Mossel and Sebastien Roch: Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep.
SIAM Journal on Discrete Mathematics, 25(2): 872893, 2011. arxiv
 Constantinos Daskalakis, Alexandros G. Dimakis and Elchanan Mossel: Connectivity and Equilibrium in Random Games.
Annals of Applied Probability, 21(3):9871016, 2011. pdf
 Constantinos Daskalakis, Elchanan Mossel and Sebastien Roch: Evolutionary Trees and the Ising Model on the Bethe Lattice: a Proof of Steel's Conjecture.
Probability Theory and Related Fields, 149(12):149189, 2011. arxiv
 Constantinos Daskalakis, Aranyak Mehta and Christos H. Papadimitriou: A Note on Approximate Nash Equilibria.
Theoretical Computer Science, 410(17), 15811588, 2009. Special Issue for WINE 2006. Invited. pdf

Constantinos Daskalakis, Paul W. Goldberg and Christos H. Papadimitriou: The Complexity of Computing a Nash Equilibrium.
SIAM Journal on Computing, 39(1), 195259, May 2009. Special issue for STOC 2006. Invited. pdf

Constantinos Daskalakis, Alexandros G. Dimakis, Richard Karp and Martin Wainwright: Probabilistic Analysis of Linear Programming Decoding.
IEEE Transactions on Information Theory, 54(8), 35653578, August 2008. arXiv
Expository Articles

Constantinos Daskalakis: Nash equilibria: Complexity, symmetries, and approximation.
Computer Science Review 3(2): 87100, 2009. pdf

Constantinos Daskalakis, Paul W. Goldberg and Christos H. Papadimitriou: The complexity of computing a Nash equilibrium.
Communications of the ACM 52(2):8997, 2009. pdf
Recent Work: 2008 (i.e. postBerkeley)present
 Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos: The Complexity of Optimal Mechanism Design.
In the 25th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), SODA 2014. arxiv
 Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, and Rocco Servedio: A Polynomialtime Approximation Scheme for Faulttolerant Distributed Storage.
In the 25th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), SODA 2014. arxiv
 Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnel, Rocco SIIRVedio and LiYang Tan: Learning Sums of Independent Integer Random Variables.
In the 54th IEEE Symposium on Foundations of Computer Science, FOCS 2013. pdf
 Yang Cai, Constantinos Daskalakis and Matt Weinberg: Understanding Incentives: Mechanism Design becomes Algorithm Design.
In the 54th IEEE Symposium on Foundations of Computer Science, FOCS 2013. arxiv
 Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos: Mechanism Design via Optimal Transport.
In the 14th ACM Conference on Electronic Commerce, EC 2013. Best Paper and Best Student Paper Award.
 Yang Cai, Constantinos Daskalakis and Matt Weinberg: Reducing Revenue to Welfare Maximization : Approximation Algorithms and other Generalizations.
In the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), SODA 2013. pdf
 Pablo Azar, Constantinos Daskalakis, Silvio Micali and Matt Weinberg: Optimal and Efficient Parametric Auctions.
In the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), SODA 2013. pdf
 Constantinos Daskalakis, Ilias Diakonikolas, Rocco Servedio, Greg Valiant and Paul Valiant: Testing kModal Distributions: Optimal Algorithms via Reductions.
In the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), SODA 2013. arxiv
 Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos: Optimal Pricing is Hard.
In the 8th Workshop on Internet & Network Economics, WINE 2012. pdf
 Yang Cai, Constantinos Daskalakis and Matt Weinberg: Optimal MultiDimensional Mechanism Design: Reducing Revenue to Welfare Maximization.
In the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), FOCS 2012. arxiv
 Constantinos Daskalakis and Matt Weinberg: Symmetries and Optimal MultiDimensional Mechanism Design.
In the 13th ACM Conference on Electronic Commerce, EC 2012. ECCC Report. Best Student Paper Award.
 Yang Cai, Constantinos Daskalakis and Matt Weinberg: An Algorithmic Characterization of MultiDimensional Mechanisms.
In the 44th ACM Symposium on Theory of Computing, STOC 2012. ECCC Report.
 Constantinos Daskalakis, Ilias Diakonikolas and Rocco A. Servedio: Learning Poisson Binomial Distributions.
In the 44th ACM Symposium on Theory of Computing, STOC 2012. arXiv
 Constantinos Daskalakis, Ilias Diakonikolas and Rocco A. Servedio: Learning kModal Distributions via Testing.
In the 23rd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2012. arXiv
 Constantinos Daskalakis and George Pierrakos: Simple, Optimal and Efficient Auctions.
In the 7th Workshop on Internet & Network Economics, WINE 2011. pdf
 Yang Cai and Constantinos Daskalakis: ExtremeValue Theorems for Optimal Multidimensional Pricing.
In the 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011. arxiv
Invited to Games and Economic Behavior (Special Issue for STOC/FOCS/SODA 2011.)
 Constantinos Daskalakis, Alexandros G. Dimakis and Elchanan Mossel: Connectivity and Equilibrium in Random Games.
Annals of Applied Probability, 21(3):9871016, 2011. pdf
 Constantinos Daskalakis, Elchanan Mossel and Sebastien Roch: Evolutionary Trees and the Ising Model on the Bethe Lattice: a Proof of Steel's Conjecture.
Probability Theory and Related Fields, 149(12):149189, 2011. arxiv

Constantinos Daskalakis: On the Complexity of Approximating a Nash Equilibrium.
In the 22nd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2011.
Transactions on Algorithms (TALG), to appear. Special Issue for SODA 2011. Invited. pdf

Constantinos Daskalakis, Alan Deckelbaum and Anthony Kim: NearOptimal NoRegret Algorithms for Zerosum Games.
In the 22nd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2011. pdf
Invited to Games and Economic Behavior (Special Issue for STOC/FOCS/SODA 2011.)

Yang Cai and Constantinos Daskalakis: On Minmax Theorems for Multiplayer Games.
In the 22nd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2011. pdf

Constantinos Daskalakis and Christos Papadimitriou: Continuous Local Search.
In the 22nd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2011. pdf
 C. Daskalakis, R. Frongillo, C. H. Papadimitriou, G. Pierrakos and G. Valiant: On Learning Algorithms for Nash Equilibria.
In the 3rd International Symposium on Algorithmic Game Theory, SAGT 2010. pdf

Constantinos Daskalakis and Sebastien Roch: AlignmentFree Phylogenetic Reconstruction.
In the 14th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2010. pdf
Also in Annals of Applied Probability, 23(2): 693721, 2013. arxiv

Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim and Sebastien Roch: Global Alignment of Molecular Sequences via Ancestral State Reconstruction.
In the 1st Symposium on Innovations in Computer Science, ICS 2010. conference version
Stochastic Processes and their Applications, 122(12): 38523874, 2012. journal version

Constantinos Daskalakis, Ilias Diakonikolas and Mihalis Yannakakis: How good is the Chord algorithm?
In the 21st Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2010. pdf

Ilan Adler, Constantinos Daskalakis and Christos H. Papadimitriou: A Note on Strictly Competitive Games.
In the 5th Workshop on Internet & Network Economics, WINE 2009. pdf

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

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

Sanjeev Arora, Constantinos Daskalakis and David Steurer: MessagePassing Algorithms and Improved LP Decoding.
In the 41st ACM Symposium On Theory of Computing, STOC 2009. pdf.
Also in IEEE Transactions on Information Theory, to appear.
 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. arxiv
Also in SIAM Journal on Discrete Mathematics, 25(2): 872893, 2011.
 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. pdf
 Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant and Paul Valiant: On the Complexity of Nash Equilibria of ActionGraph Games.
In the 20th Annual ACMSIAM Symposium On Discrete Algorithms, SODA 2009. arxiv
 Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld and Elad Verbin: Sorting and Ranking in Partially Ordered Sets.
In the 20th Annual ACMSIAM Symposium On Discrete Algorithms, SODA 2009. arxiv
SIAM Journal on Computing, 40(3): 597622, 2011.
 Constantinos Daskalakis: An Efficient PTAS for TwoStrategy Anonymous Games.
In the 4th Workshop on Internet and Network Economics, WINE 2008. 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. arxiv
Complete List of Publications by Topic
Algorithmic Game Theory
 Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos: The Complexity of Optimal Mechanism Design.
In the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), SODA 2014. arxiv
 Yang Cai, Constantinos Daskalakis and Matt Weinberg: Understanding Incentives: Mechanism Design becomes Algorithm Design.
In the 54th IEEE Symposium on Foundations of Computer Science, FOCS 2013. arxiv
 Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos: Mechanism Design via Optimal Transport.
In the 14th ACM Conference on Electronic Commerce, EC 2013. Best Paper and Best Student Paper Award.
 Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos: Optimal Pricing is Hard.
In the 8th Workshop on Internet & Network Economics, WINE 2012. pdf
 Yang Cai, Constantinos Daskalakis and Matt Weinberg: Reducing Revenue to Welfare Maximization : Approximation Algorithms and other Generalizations.
In the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), SODA 2013. pdf
 Pablo Azar, Constantinos Daskalakis, Silvio Micali and Matt Weinberg: Optimal and Efficient Parametric Auctions.
In the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), SODA 2013. pdf
 Yang Cai, Constantinos Daskalakis and Matt Weinberg: Optimal MultiDimensional Mechanism Design: Reducing Revenue to Welfare Maximization.
In the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), FOCS 2012. arxiv
 Constantinos Daskalakis and Matt Weinberg: Symmetries and Optimal MultiDimensional Mechanism Design.
In the 13th ACM Conference on Electronic Commerce, EC 2012. ECCC Report. Best Student Paper Award.
 Yang Cai, Constantinos Daskalakis and Matt Weinberg: An Algorithmic Characterization of MultiDimensional Mechanisms.
In the 44th ACM Symposium on Theory of Computing, STOC 2012. ECCC Report, 2011.
 Constantinos Daskalakis and George Pierrakos: Simple, Optimal and Efficient Auctions.
In the 7th Workshop on Internet & Network Economics, WINE 2011. pdf
 Yang Cai and Constantinos Daskalakis: ExtremeValue Theorems for Optimal Multidimensional Pricing.
In the 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011. arxiv
Invited to Games and Economic Behavior (Special Issue for STOC/FOCS/SODA 2011.)
 Constantinos Daskalakis, Alexandros G. Dimakis and Elchanan Mossel: Connectivity and Equilibrium in Random Games.
Annals of Applied Probability, Volume 21(3):9871016, 2011.
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 playernodes.
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 nonexistence 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 ErdosRenyi, 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 nonmonotone 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",
journal = {Annals of Applied Probability},
year = {2011},
volume = {21},
pages = {9871016},
number = {3},
}
[abstract] [bib] [arXiv]

Constantinos Daskalakis: On the Complexity of Approximating a Nash Equilibrium.
In the 22nd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2011. pdf
Journal version in Transactions on Algorithms (TALG), to appear. Special Issue for SODA 2011. Invited. pdf

Constantinos Daskalakis, Alan Deckelbaum and Anthony Kim: NearOptimal NoRegret Algorithms for Zerosum Games.
In the 22nd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2011. pdf
Invited to Games and Economic Behavior (Special Issue for STOC/FOCS/SODA 2011.)

Yang Cai and Constantinos Daskalakis: On Minmax Theorems for Multiplayer Games.
In the 22nd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2011. pdf

Constantinos Daskalakis and Christos Papadimitriou: Continuous Local Search.
In the 22nd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2011. pdf
 C. Daskalakis, R. Frongillo, C. H. Papadimitriou, G. Pierrakos and G. Valiant: On Learning Algorithms for Nash Equilibria.
In the 3rd International Symposium on Algorithmic Game Theory, SAGT 2010. pdf

Ilan Adler, Constantinos Daskalakis and Christos H. Papadimitriou: A Note on Strictly Competitive Games.
In the 5th Workshop on Internet & Network Economics, WINE 2009.
Strictly competitive games are a class of 2player games often quoted in the literature to be a proper generalization of zerosum games. Other times it is claimed, e.g. by Aumann, that strictly competitive games are only payoff transformations of zerosum games. But to the best of our knowledge there is no proof of such claim. We shed light to this point of confusion in the literature, showing that any strictly competitive game is indeed a payoff transformation of a zero sumgame; in fact, an affine transformation. We offer two proofs of this fact, one combinatorial and one algebraic.
@inproceedings{ADP:SCGs,
title = "A Note on Strictly Competitive Games",
author = "Ilan Adler and Constantinos Daskalakis and Christos H. Papadimitriou",
year = "2009",
booktitle = "WINE",
}
[abstract] [bib] [pdf]
 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.
We consider graphical games in which the edges are zerosum games
between the endpoints/players; the payoff of a player is the sum of
the payoffs from each incident edge. Such games are arguably very
broad and useful models of networked economic interactions. We give a simple reduction of
such games to twoperson zerosum games; as a corollary, a mixed
Nash equilibrium can be computed efficiently by solving a linear
program and rounding off the results. Our
results render polynomially efficient, and simplify considerably,
the approach in [Bregman and Fokin '98].
@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] [pdf]
 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 sizethen 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 smallO(1/n)values, and therefore largeOmega(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 PPADcomplete [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 epsilonNash 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 quasipolynomial 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)) nonoblivious 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] [arXiv]
 Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant and Paul Valiant: On the Complexity of Nash Equilibria of ActionGraph Games.
In the 20th Annual ACMSIAM Symposium On Discrete Algorithms, SODA 2009.
In light of much recent interest in finding a model of multiplayer multiaction 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 actiongraph games (AGGs). AGGs, introduced by Bhat and LeytonBrown, 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 agenttypes is unconstrained, it is NPomplete to decide the existence of a purestrategy Nash equilibrium and PPADcomplete 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 purestrategy Nash equilibrium is NPcomplete and computing a mixed Nash is PPADomplete. 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 multiplayer 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 ActionGraph 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 TwoStrategy Anonymous Games.
In the 4th Workshop on Internet and Network Economics, WINE 2008.
We present a novel polynomial time approximation scheme for twostrategy 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 epsilonapproximate Nash equilibrium of an nplayer 2strategy 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 epsilonapproximate 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 TwoStrategy 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 2strategy 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 kdimensional 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 epscover 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 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 epsapproximate 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 epsapproximate Nash equilibrium (with supports of size at most two) can be computed in polynomial time in any 2player 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 epsapproximate Nash equilibrium in 2player 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.
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, lineartime algorithm examining just two strategies per player and resulting in a 1/2 approximate Nash equilibrium in any 2player game. For the more demanding notion of wellsupported 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 winlose games (games with all utilities 01), and that an approximation of 5/6 is possible contingent upon a graphtheoretic 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]
Journal version in Theoretical Computer Science, 410(17), 15811588, 2009. (Invited, special issue for WINE 2006.)
 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 PPADcomplete 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 twoplayer 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
NPcomplete 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, ThreePlayer Games Are Hard,
Manuscript 2005.
We prove that computing a Nash equilibrium in a 3player game is PPADcomplete, solving a problem left open in our result on the complexity of Nash equilibria.
@inproceedings{DP: three players,
title = "ThreePlayer 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.
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 recentlyestablished equivalence
between polynomialtime solvability of normalform games and
graphical games, and shows that these kinds of games can implement
arbitrary members of a PPADcomplete 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]
Journal version in SIAM Journal on Computing, 39(1), 195259, May 2009. (Invited, special issue for STOC 2006.)
Expository article in Communications of the ACM 52(2):8997, 2009. (Invited.)
 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 onedimensional highlyregular game is NLcomplete, whereas if the game is multidimensional it is NEXPcomplete. 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 undergrad 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 and Sebastien Roch: AlignmentFree Phylogenetic Reconstruction.
In the 14th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2010. conference version
Journal version in Annals of Applied Probability, 23(2): 693721, 2013. journal version

Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim and Sebastien Roch: Global Alignment of Molecular Sequences via Ancestral State Reconstruction.
First Symposium on Innovations in Computer Science, ICS 2010.
Molecular phylogenetic techniques do not generally account for such
common evolutionary events as site insertions and deletions (known as
indels). Instead tree building algorithms and ancestral state
inference procedures typically rely on substitutiononly models of
sequence evolution. In practice these methods are extended beyond this
simplified setting with the use of heuristics that produce global
alignments of the input sequencesan important problem which has no
rigorous modelbased solution. In this paper we open a new direction
on this topic by considering a version of the multiple sequence
alignment in the context of stochastic indel models. More precisely,
we introduce the following {\em trace reconstruction problem on a
tree} (TRPT): a binary sequence is broadcast through a tree channel
where
we allow substitutions, deletions, and insertions; we seek
to reconstruct the original sequence from the sequences
received at the leaves of the tree. We give a recursive
procedure for this problem with strong reconstruction
guarantees at low mutation rates, providing also an alignment of the
sequences at the leaves of the tree. The TRPT problem without indels
has been studied in previous work (Mossel 2004, Daskalakis et al.
2006) as a bootstrapping step towards obtaining
informationtheoretically optimal phylogenetic reconstruction methods.
The present work sets up a framework for extending these works to
evolutionary models with indels.
In the TRPT problem we begin with a random sequence $x_1, \ldots, x_k$ at the root of a $d$ary tree. If vertex $v$ has the sequence $y_1, \ldots y_{k_{v}}$, then each one of its $d$ children will have a sequence which is generated from $y_1, \ldots y_{k_{v}}$ by flipping three biased coins for each bit. The first coin has probability $p_s$ for Heads, and determines whether this bit will be substituted or not. The second coin has probability $p_d$, and determines whether this bit will be deleted, and the third coin has probability $p_i$ and determines whether a new random bit will be inserted. The input to the procedure is the sequences of the $n$ leaves of the tree, as well as the tree structure (but not the sequences of the inner vertices) and the goal is to reconstruct an approximation to the sequence of the root (the DNA of the ancestral father). For every $\epsilon > 0$, we present a deterministic algorithm which outputs an approximation of $x_1, \ldots, x_k$ if $\prbi + \prbd < O(1/k^{2/3} \log n)$ and $(1  2\prbs)^2 > O(d^{1} \log d)$.
To our knowledge, this is the first rigorous trace reconstruction result on a tree in the presence of indels.
@inproceedings{ADHR:AncestralReconstruction,
title = "Global Alignment of Molecular Sequences via Ancestral State Reconstruction",
author = "Alexandr Andoni and Constantinos Daskalakis and Avinatan Hassidim and Sebastien Roch",
year = "2010",
booktitle = "ICS",
}
[abstract] [bib] [arxiv]
Journal version in Stochastic Processes and their Applications, 122(12): 38523874, 2012. journal version
 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 distancebased 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] [arXiv]
Journal version in SIAM Journal on Discrete Mathematics, 25(2): 872893, 2011.
 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 CavenderFarrisNeyman model of evolution, if the mutation probability p on all edges of the tree satisfies 2(12p)^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 CavenderFarrisNeyman model, since, if the mutation probability does not satisfy 2(12p)^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 JukesCantor 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]
Journal version in Probability Theory and Related Fields, 149(12):149189, 2011.
 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 distancebased
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 edgedisjoint 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
 Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, and Rocco Servedio: A Polynomialtime Approximation Scheme for Faulttolerant Distributed Storage.
In the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), SODA 2014. arxiv
 Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnel, Rocco SIIRVedio and LiYang Tan: Learning Sums of Independent Integer Random Variables.
In the 54th IEEE Symposium on Foundations of Computer Science, FOCS 2013. pdf
 Constantinos Daskalakis, Ilias Diakonikolas, Rocco Servedio, Greg Valiant and Paul Valiant: Testing kModal Distributions: Optimal Algorithms via Reductions.
In the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), SODA 2013. arxiv
 Constantinos Daskalakis, Ilias Diakonikolas and Rocco A. Servedio: Learning Poisson Binomial Distributions.
In the 44th ACM Symposium on Theory of Computing, STOC 2012.
arXiv
 Constantinos Daskalakis, Ilias Diakonikolas and Rocco A. Servedio: Learning kModal Distributions via Testing.
In the 23rd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2012. arXiv

Sanjeev Arora, Constantinos Daskalakis and David Steurer: MessagePassing Algorithms and Improved LP Decoding.
In the 41st ACM Symposium On Theory of Computing, STOC 2009.
Linear programming decoding for lowdensity parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performancecoming close to that of iterative decoding algorithmsand its amenability to finiteblocklength 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.05fraction of correctable errors for rate1/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 nearlinear time by a "reweighted" version of the minsum algorithm, obviating the need for linear programming. Our analysis implies, in particular, that this reweighted version of the minsum decoder corrects up to a 0.05fraction of errors.
@inproceedings{ADS: Improved LP decoding,
title = "MessagePassing Algorithms and Improved LP Decoding",
author = "Sanjeev Arora and Constantinos Daskalakis and David Steurer",
year = "2009",
booktitle = "STOC",
}
[abstract] [bib] [pdf]
Journal version in IEEE Transactions on Information Theory, 58(12): 72607271, 2012.

Constantinos Daskalakis, Alexandros G. Dimakis, Richard Karp and Martin Wainwright: Probabilistic Analysis
of Linear Programming Decoding.
In the 18th Annual ACMSIAM Symposium On Discrete Algorithms, SODA 2007.
We initiate the probabilistic analysis of linear programming (LP)
decoding of lowdensity paritycheck (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
nonasymptotic results for LDPC codes, and in particular exceeds
the best previous finitelength result on LP decoding by a factor
greater than ten. This improvement stems in part from our analysis
of probabilistic bitflipping 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 byproduct 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]
Journal version in IEEE Transactions on Information Theory, 54(8), 35653578, August 2008. 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 firstmoveradvantage phase, a
fitgetricher phase and an innovationpaysoff
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 Topics

Constantinos Daskalakis, Ilias Diakonikolas and Mihalis Yannakakis: How good is the Chord algorithm?.
In the 21st Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2010. pdf
 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 ACMSIAM 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 widthw 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 kselection 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 kselection 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]
Journal version in SIAM Journal on Computing, 40(3): 597622, 2011.
 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 ExclusiveSumofProducts Minimization. Our algorithm is compared to the stateofthe art algorithm used in most CADprograms. 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]