Constantinos Daskalakis

• >main
• academic work
• >contact

Bio at a Glance

CSAIL, EECS, MIT
Avanessians Professor, 2022 - present
Professor, 2018 - 2022
Associate Professor (with tenure), 2015 - 2018
X-Window Consortium Associate Professor, 2012 - 2015
X-Window Consortium Assistant Professor, 2011 - 2012
Assistant Professor, 2009 - 2011

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

UNIVERSITY OF CALIFORNIA, BERKELEY
Ph.D. in Computer Science, 2004-2008
Thesis: The Complexity of Nash Equilibria
Advisor: Christos H. Papadimitriou

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

Publications

Chronological list, journal papers, expository articles

or clustered by topic: Economics, Game theory, and their interface with Computation, Machine Learning, Statistics, and Probability, and Computational Biology.

Journal Publications

Expository Articles

Publications in Chronological Order

List of Publications by Topic

Interface of Computation with Economics and Game Theory

• Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich: From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces.
  In the 56th ACM Symposium on Theory of Computing, STOC 2024. arXiv. twitter summary

• Constantinos Daskalakis, Noah Golowich, Nika Haghtalab, Abhishek Shetty: Smooth Nash Equilibria: Algorithms and Complexity.
  In the 15th Innovations in Theoretical Computer Science (ITCS), ITCS 2024. arXiv.

• Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson: Online Learning and Solving Infinite Games with an ERM Oracle.
  In the 35th Annual Conference on Learning Theory, COLT 2023. arXiv.

• Constantinos Daskalakis, Noah Golowich, Stratis Skoulakis, Manolis Zampetakis: STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games.
  In the 35th Annual Conference on Learning Theory, COLT 2023. arXiv.

• Constantinos Daskalakis, Noah Golowich, Kaiqing Zhang: The Complexity of Markov Equilibrium in Stochastic Games.
  In the 35th Annual Conference on Learning Theory, COLT 2023. arXiv.

• Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, Manolis Zampetakis: What Makes A Good Fisherman? Linear Regression under Self-Selection Bias.
  In the 55th ACM Symposium on Theory of Computing, STOC 2023. arXiv.

• Yang Cai, Constantinos Daskalakis: Recommender Systems meet Mechanism Design.
  In the 23rd ACM Conference on Economics and Computation, EC 2022. arXiv.

• Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, Manolis Zampetakis: Estimation of Standard Auction Models.
  In the 23rd ACM Conference on Economics and Computation, EC 2022. arXiv.

• Constantinos Daskalakis, Noah Golowich: Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games.
  In the 54th ACM Symposium on Theory of Computing, STOC 2022. arXiv.

• Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, Tuomas Sandholm: Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games.
  In the 54th ACM Symposium on Theory of Computing, STOC 2022. arXiv.

• Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich: Near-Optimal No-Regret Learning in General Games.
  In the 35th Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2021. Oral. arXiv. twitter summary

• Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis: The Complexity of Constrained Min-Max Optimization.
  In the 53rd ACM Symposium on Theory of Computing, STOC 2021. arXiv. twitter summary

• Jelena Diakonikolas, Constantinos Daskalakis, Michael I. Jordan: Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization.
  In the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), AISTATS 2021. arXiv

• Fotini Christia, Michael Curry, Constantinos Daskalakis, Erik Demaine, John P. Dickerson, MohammadTaghi Hajiaghayi, Adam Hesterberg, Marina Knittel, Aidan Milliff: Scalable Equilibrium Computation in Multi-agent Influence Games on Networks.
  In the 34th AAAI Conference on Artificial Intelligence, AAAI 2021. arXiv

• Noah Golowich, Sarath Pattathil, Constantinos Daskalakis: Tight last-iterate convergence rates for no-regret learning in multi-player games.
  In the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2020. arXiv

• Constantinos Daskalakis, Dylan Foster, Noah Golowich: Independent Policy Gradient Methods for Competitive Reinforcement Learning.
  In the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2020. arXiv

• Constantinos Daskalakis, Manolis Zampetakis: More Revenue from Two Samples via Factor Revealing SDPs.
  In the 21st ACM Conference on Economics and Computation, EC 2020. pdf

• Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, Santhoshini Velusamy: Simple, Credible, and Approximately-Optimal Auctions.
  In the 21st ACM Conference on Economics and Computation, EC 2020. arXiv

• Johannes Brustle, Yang Cai, Constantinos Daskalakis: Multi-Item Mechanisms without Item-Independence: Learnability via Robustness.
  In the 21st ACM Conference on Economics and Computation, EC 2020. arXiv

• Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, Asuman Ozdaglar: Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems.
  In the 33nd Annual Conference on Learning Theory, COLT 2020. arXiv

• Constantinos Daskalakis, Ioannis Panageas: Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization.
  In the 10th Innovations in Theoretical Computer Science (ITCS) conference, ITCS 2019. arXiv.

• Shipra Agrawal, Constantinos Daskalakis, Vahab Mirrokni, Balasubramanian Sivan: Robust Repeated Auctions under Heterogeneous Buyer Behavior.
  In the 19th ACM conference on Economics and Computation, EC 2018. arxiv.

• Yang Cai and Constantinos Daskalakis: Learning Multi-Item Auctions with (or without) Samples.
  In the 58th IEEE Symposium on Foundations of Computer Science (FOCS), FOCS 2017. arxiv

• Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos: Strong Duality for a Multiple-Good Monopolist.
  Econometrica, 85(3):735-767, 2017. arXiv

• Constantinos Daskalakis and Vasilis Syrgkanis: Learning in Auctions: Regret is Hard, Envy is Easy.
  In the 57th IEEE Symposium on Foundations of Computer Science (FOCS), FOCS 2016. arxiv

• Aviv Adler, Constantinos Daskalakis and Erik Demaine: The Complexity of Hex and the Jordan Curve Theorem.
  In the 43rd International Colloquium on Automata, Languages and Programming, ICALP 2016. pdf

• Itai Ashlagi, Constantinos Daskalakis and Nima Haghpanah: Sequential Mechanisms with Ex-post Participation Guarantees..
  In the 17th ACM Conference on Economics and Computation (EC), EC 2016. Invited to Special Issue. arxiv

• Constantinos Daskalakis, Christos Papadimitriou and Christos Tzamos: Does Information Revelation Improve Revenue?.
  In the 17th ACM Conference on Economics and Computation (EC), EC 2016. Invited to Special Issue. pdf

• Yang Cai, Ozan Candogan, Constantinos Daskalakis and Christos Papadimitriou: Zero-sum Polymatrix Games: A Generalization of Minmax.
  Mathematics of Operations Research, 41(2): 648-655, 2016. pdf

• Constantinos Daskalakis and Christos Papadimitriou: Approximate Nash Equilibria in Anonymous Games.
  Journal of Economic Theory, 156:207--245, 2015. pdf

• Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos: Strong Duality for a Multiple-Good Monopolist.
  In the 16th ACM Conference on Economics and Computation (EC), EC 2015. arXiv

• Constantinos Daskalakis, Nikhil Devanur and Matt Weinberg: Revenue Maximization and Ex-Post Budget Constraints.
  In the 16th ACM Conference on Economics and Computation (EC), EC 2015.arxiv

• Constantinos Daskalakis and Matt Weinberg: Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms.
  In the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA 2015. arXiv

• Constantinos Daskalakis and Qinxuan Pan: A Counter-Example to Karlin's Strong Conjecture for Fictitious Play.
  In the 55th IEEE Symposium on Foundations of Computer Science, FOCS 2014. arxiv

• Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos: The Complexity of Optimal Mechanism Design.
  In the 24th Annual ACM-SIAM 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. pdf

• 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 ACM-SIAM 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 ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA 2013. pdf

• Yang Cai, Constantinos Daskalakis and Matt Weinberg: Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization.
  In the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), FOCS 2012. FOCS 2022 Test of Time Award. arxiv

• Constantinos Daskalakis and Matt Weinberg: Symmetries and Optimal Multi-Dimensional 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 Multi-Dimensional 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: Extreme-Value Theorems for Optimal Multidimensional Pricing.
  In the 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011. arxiv
  Games and Economic Behavior, 92:266--305, 2015. Special Issue for STOC/FOCS/SODA 2011. Invited. arxiv

• Constantinos Daskalakis, Alexandros G. Dimakis and Elchanan Mossel: Connectivity and Equilibrium in Random Games.
  Annals of Applied Probability, Volume 21(3):987-1016, 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 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",
    journal = {Annals of Applied Probability},
    year = {2011},
    volume = {21},
    pages = {987-1016},
    number = {3},
  }
  

  [abstract] [bib] [arXiv]
  

• Constantinos Daskalakis: On the Complexity of Approximating a Nash Equilibrium.
  In the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. pdf
  ACM Transactions on Algorithms (TALG), 9(3): 23, 2013. Special Issue for SODA 2011. Invited. pdf

• Constantinos Daskalakis, Alan Deckelbaum and Anthony Kim: Near-Optimal No-Regret Algorithms for Zero-sum Games.
  In the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. pdf
  Games and Economic Behavior, 92:327-348, 2015. Special Issue for STOC/FOCS/SODA 2011. Invited. pdf

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

• Constantinos Daskalakis and Christos Papadimitriou: Continuous Local Search.
  In the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. pdf and corrigendum
  

• 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 2-player games often quoted in the literature to be a proper generalization of zero-sum games. Other times it is claimed, e.g. by Aumann, that strictly competitive games are only payoff transformations of zero-sum 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 sum-game; 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 zero-sum 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 two-person zero-sum 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 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] [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 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.

  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]
  
  Journal version in Theoretical Computer Science, 410(17), 1581--1588, 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 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.

  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]
  
  Journal version in SIAM Journal on Computing, 39(1), 195--259, May 2009. (Invited, special issue for STOC 2006.)
  Expository article in Communications of the ACM 52(2):89--97, 2009. (Invited.)
  2008 Kalai Prize from Game Theory Society; 2011 SIAM Outstanding Paper Prize; 2022 ACM SIGECOM Test of Time Award.
  

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

 

Machine Learning, Statistics and Probability

• Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich: From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces.
  In the 56th ACM Symposium on Theory of Computing, STOC 2024. arXiv. twitter summary

• Giannis Daras, Yuval Dagan, Alexandros G. Dimakis, Constantinos Daskalakis: Consistent Diffusion Models: Mitigating Sampling Drift by Learning to be Consistent.
  In the 37th Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2023. arXiv.

• Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson: Online Learning and Solving Infinite Games with an ERM Oracle.
  In the 35th Annual Conference on Learning Theory, COLT 2023. arXiv.

• Constantinos Daskalakis, Noah Golowich, Stratis Skoulakis, Manolis Zampetakis: STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games.
  In the 35th Annual Conference on Learning Theory, COLT 2023. arXiv.

• Constantinos Daskalakis, Noah Golowich, Kaiqing Zhang: The Complexity of Markov Equilibrium in Stochastic Games.
  In the 35th Annual Conference on Learning Theory, COLT 2023. arXiv.

• Davin Choo, Yuval Dagan, Constantinos Daskalakis, Anthimos-Vardis Kandiros: Learning and Testing Latent-Tree Ising Models Efficiently.
  In the 35th Annual Conference on Learning Theory, COLT 2023. arXiv.

• Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, Manolis Zampetakis: What Makes A Good Fisherman? Linear Regression under Self-Selection Bias.
  In the 55th ACM Symposium on Theory of Computing, STOC 2023. arXiv.

• Giannis Daras, Yuval Dagan, Alex Dimakis, Constantinos Daskalakis: Score-Guided Intermediate Level Optimization: Fast Langevin Mixing for Inverse Problems.
  In the 39th International Conference on Machine Learning, ICML 2022. arXiv.

• Yuval Dagan, Vardis Kandiros, Constantinos Daskalakis: EM's Convergence in Gaussian Latent Tree Models.
  In the 35th Annual Conference on Learning Theory, COLT 2022. arXiv.

• Yang Cai, Constantinos Daskalakis: Recommender Systems meet Mechanism Design.
  In the 23rd ACM Conference on Economics and Computation, EC 2022. arXiv.

• Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, Manolis Zampetakis: Estimation of Standard Auction Models.
  In the 23rd ACM Conference on Economics and Computation, EC 2022. arXiv.

• Constantinos Daskalakis, Noah Golowich: Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games.
  In the 54th ACM Symposium on Theory of Computing, STOC 2022. arXiv.

• Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, Tuomas Sandholm: Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games.
  In the 54th ACM Symposium on Theory of Computing, STOC 2022. arXiv.

• Constantinos Daskalakis, Petros Dellaportas, Ares Panos: How Good are Low-Rank Approximations in Gaussian Process Regression?
  In the 36th AAAI Conference on Artificial Intelligence (AAAI), AAAI 2022. arxiv.

• Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich: Near-Optimal No-Regret Learning in General Games.
  In the 35th Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2021. Oral. arXiv. twitter summary

• Constantinos Daskalakis, Patroklos Stefanou, Rui Yao, Manolis Zampetakis: Efficient Truncated Linear Regression with Unknown Noise Variance.
  In the 35th Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2021. arXiv.

• Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Surbhi Goel, Anthimos Vardis Kandiros: Statistical Estimation from Dependent Data.
  In the 38th International Conference on Machine Learning, ICML 2021. arXiv.

• Constantinos Daskalakis, Vasilis Kontonis, Christos Tzamos, Manolis Zampetakis: A Statistical Taylor Theorem and Extrapolation of Truncated Densities.
  In the 34th Annual Conference on Learning Theory, COLT 2021. arXiv.

• Constantinos Daskalakis, Qinxuan Pan: Sample-Optimal and Efficient Learning of Tree Ising models.
  In the 53rd ACM Symposium on Theory of Computing, STOC 2021. arXiv. twitter summary

• Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis: The Complexity of Constrained Min-Max Optimization.
  In the 53rd ACM Symposium on Theory of Computing, STOC 2021. arXiv. twitter summary

• Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Anthimos Vardis Kandiros: Learning Ising Models from One or Multiple Samples.
  In the 53rd ACM Symposium on Theory of Computing, STOC 2021. arXiv. twitter summary

• Jelena Diakonikolas, Constantinos Daskalakis, Michael I. Jordan: Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization.
  In the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), AISTATS 2021. arXiv

• Mucong Ding, Constantinos Daskalakis, Soheil Feizi: GANs with Conditional Independence Graphs: On Subadditivity of Probability Divergences.
  In the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), AISTATS 2021. Oral. arXiv

• Noah Golowich, Sarath Pattathil, Constantinos Daskalakis: Tight last-iterate convergence rates for no-regret learning in multi-player games.
  In the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2020. arXiv

• Constantinos Daskalakis, Dylan Foster, Noah Golowich: Independent Policy Gradient Methods for Competitive Reinforcement Learning.
  In the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2020. arXiv

• Constantinos Daskalakis, Dhruv Rohatgi, Manolis Zampetakis: Truncated Linear Regression in High Dimensions.
  In the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2020. arXiv

• Constantinos Daskalakis, Dhruv Rohatgi, Manolis Zampetakis: Constant-Expansion Suffices for Compressed Sensing with Generative Priors.
  In the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2020. Spotlight. arXiv

• Qi Lei, Jason D. Lee, Alexandros G. Dimakis, Constantinos P. Daskalakis: SGD Learns One-Layer Networks in WGANs.
  In the 37th International Conference on Machine Learning, ICML 2020. arXiv

• Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, Asuman Ozdaglar: Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems.
  In the 33nd Annual Conference on Learning Theory, COLT 2020. arXiv

• Constantinos Daskalakis, Nishanth Dikkala, Ioannis Panageas: Logistic regression with peer-group effects via inference in higher-order Ising models.
  In the 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020. arXiv.

• Constantinos Daskalakis, Andrew Ilyas, Manolis Zampetakis: A Theoretical and Practical Framework for Regression and Classification from Truncated Samples.
  In the 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020. pdf.

• Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, Manolis Zampetakis: Computationally and Statistically Efficient Truncated Regression.
  In the 32nd Annual Conference on Learning Theory, COLT 2019. arXiv.

• Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Siddhartha Jayanti: Generalization and learning under Dobrushin's condition.
  In the 32nd Annual Conference on Learning Theory, COLT 2019. arXiv.

• Constantinos Daskalakis, Nishanth Dikkala, Ioannis Panageas: Regression from Dependent Observations.
  In the 51st Annual ACM Symposium on the Theory of Computing, STOC 2019. arXiv

• Andrew Ilyas, Ajil Jalal, Eirini Asteri, Constantinos Daskalakis, Alexandros G. Dimakis: The Robust Manifold Defense: Adversarial Training using Generative Models.
  arXiv.

• Constantinos Daskalakis, Ioannis Panageas: Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization.
  In the 10th Innovations in Theoretical Computer Science (ITCS) conference, ITCS 2019. arXiv.

• Constantinos Daskalakis, Ioannis Panageas: The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization.
  In the 32nd Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2018. arXiv.

• Constantinos Daskalakis, Nishanth Dikkala, Siddhartha Jayanti: HOGWILD!-Gibbs can be PanAccurate.
  In the 32nd Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2018. arXiv.

• Nima Anari, Constantinos Daskalakis, Wolfgang Maass, Christos Papadimitriou, Amin Saberi, Santosh Vempala: Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons.
  In the 32nd Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2018. arXiv.

• Jayadev Acharya, Arnab Bhattacharyya, Constantinos Daskalakis, Saravanan Kandasamy: Learning and Testing Causal Models with Interventions.
  In the 32nd Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2018. arXiv.

• Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, Manolis Zampetakis: Efficient Statistics, in High Dimensions, from Truncated Samples.
  In the 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. arXiv.

• Constantinos Daskalakis, Nishanth Dikkala, Nick Gravin: Testing Symmetric Markov Chains from a Single Trajectory.
  In the 31st Annual Conference on Learning Theory, COLT 2018. arxiv.

• Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, Haoyang Zeng: Training GANs with Optimism.
  In the 6th International Conference on Learning Representations, ICLR 2018. arXiv.

• Constantinos Daskalakis, Christos Tzamos, Manolis Zampetakis: Bootstrapping EM via EM and Convergence Analysis in the Naive Bayes Model.
  In the 21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018. pdf

• Constantinos Daskalakis, Christos Tzamos and Manolis Zampetakis: A Converse to Banach's Fixed Point Theorem and its CLS Completeness.
  In the 50th Annual ACM Symposium on the Theory of Computing, STOC 2018. arXiv

• Constantinos Daskalakis, Gautam Kamath and John Wright: Which Distribution Distances are Sublinearly Testable?.
  In the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. arXiv

• Constantinos Daskalakis, Nishanth Dikkala and Gautam Kamath: Testing Ising Models.
  In the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. arXiv

• Constantinos Daskalakis, Nishanth Dikkala and Gautam Kamath: Concentration of Multilinear Functions of the Ising Model with Applications to Network Data.
  In the 31st Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2017. arXiv

• Constantinos Daskalakis and Yasushi Kawase: Optimal Stopping Rules for Sequential Hypothesis Testing.
  In the 25th Annual European Symposium on Algorithms (ESA), ESA 2017. pdf

• Bryan Cai, Constantinos Daskalakis and Gautam Kamath: Priv'IT: Private and Sample Efficient Identity Testing.
  In the 34th International Conference on Machine Learning, ICML 2017. arXiv

• Constantinos Daskalakis, Christos Tzamos and Manolis Zampetakis: Ten Steps of EM Suffice for Mixtures of Two Gaussians.
  In the 30th Annual Conference on Learning Theory, COLT 2017. Preliminary version presented at NeurIPS 2016 Workshop on Non-Convex Optimization for Machine Learning. arXiv

• Constantinos Daskalakis and Qinxuan Pan: Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing.
  In the 30th Annual Conference on Learning Theory, COLT 2017. arXiv

• Constantinos Daskalakis, Anindya De, Gautam Kamath and Christos Tzamos: A Size-Free CLT for Poisson Multinomials and its Applications.
  In the 48th ACM Symposium on Theory of Computing, STOC 2016. arXiv

• Constantinos Daskalakis and Christos Papadimitriou: Sparse Covers for Sums of Indicators.
  Probability Theory and Related Fields, 162(3):679-705, 2015. arXiv

• Jayadev Acharya, Constantinos Daskalakis and Gautam Kamath: Optimal Testing for Properties of Distributions.
  In the 29th Annual Conference on Neural Information Processing Systems (NeurIPS), NeurIPS 2015. Spotlight. arXiv

• Constantinos Daskalakis, Gautam Kamath and Christos Tzamos: On the Structure, Covering, and Learning of Poisson Multinomial Distributions.
  In the 56th IEEE Symposium on Foundations of Computer Science (FOCS), FOCS 2015. arXiv

• Yang Cai, Constantinos Daskalakis and Christos H. Papadimitriou: Optimum Statistical Estimation with Strategic Data Sources.
  In the 28th Annual Conference on Learning Theory (COLT), COLT 2015. arXiv

• Constantinos Daskalakis and Jayadev Acharya: Testing Poisson Binomial Distributions.
  In the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA 2015. arXiv

• Constantinos Daskalakis and Gautam Kamath: Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians.
  In the 27th Annual Conference on Learning Theory (COLT), COLT 2014. arxiv

• Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, and Rocco Servedio: A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage.
  In the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA 2014. arxiv

• Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnel, Rocco SIIRVedio and Li-Yang 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 k-Modal Distributions: Optimal Algorithms via Reductions.
  In the 24th Annual ACM-SIAM 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
  Algorithmica, 72(1):316-357, 2015. Special Issue on New Theoretical Challenges in Machine Learning. Invited. arXiv

• Constantinos Daskalakis, Ilias Diakonikolas and Rocco A. Servedio: Learning k-Modal Distributions via Testing.
  In the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. arXiv

• 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.
  IEEE Transactions on Information Theory, 58(12):7260--7271, 2012. pdf

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

  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]
  
  Journal version in IEEE Transactions on Information Theory, 54(8), 3565-3578, 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 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] [arxiv]
  

 

Computational Biology

• Davin Choo, Yuval Dagan, Constantinos Daskalakis, Anthimos-Vardis Kandiros: Learning and Testing Latent-Tree Ising Models Efficiently.
  In the 35th Annual Conference on Learning Theory, COLT 2023. arXiv.

• Yuval Dagan, Vardis Kandiros, Constantinos Daskalakis: EM's Convergence in Gaussian Latent Tree Models.
  In the 35th Annual Conference on Learning Theory, COLT 2022. arXiv.

• Constantinos Daskalakis and Sebastien Roch: Species Trees from Gene Trees Despite a High Rate of Lateral Genetic Transfer: A Tight Bound.
  In the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA 2016. arXiv

• Constantinos Daskalakis and Sebastien Roch: Alignment-Free 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): 693--721, 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 substitution-only 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 sequences---an important problem which has no rigorous model-based 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 information-theoretically 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): 3852--3874, 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 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] [arXiv]
  
  Journal version in SIAM Journal on Discrete Mathematics, 25(2): 872-893, 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 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]
  
  Journal version in Probability Theory and Related Fields, 149(1-2):149-189, 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 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]
  

 

Other Topics

• Constantinos Daskalakis, Ilias Diakonikolas and Mihalis Yannakakis: How good is the Chord algorithm?.
  In the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010. pdf
  SIAM Journal on Computing, 45(3): 811-858, 2016. 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 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]
  
  Journal version in SIAM Journal on Computing, 40(3): 597-622, 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  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]
  

[Accessibility]