Constantinos Daskalakis

    Associate Professor, EECS, MIT

Short Bio

CSAIL, EECS, MIT
Associate Professor (with tenure), 2015 - present
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
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, 1999-2004
Thesis: On the Existence of Pure Nash Equilibria in Graphical Games with succinct description
Advisor: Stathis Zachos
GPA: 9.98/10.00 (Summa Cum Laude)

Publications

Chronological list, journal papers, expository articles

or clustered by topic: Economics, Game theory, and their interface with Computation, computational biology, learning, statistics, and probability.

Journal Publications

  • Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos: Strong Duality for a Multiple-Good Monopolist.
    Econometrica, to appear. arXiv
  • Constantinos Daskalakis, Ilias Diakonikolas and Mihalis Yannakakis: How good is the Chord algorithm?
    SIAM Journal on Computing, 45(3): 811-858, 2016. 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: Sparse Covers for Sums of Indicators.
    Probability Theory and Related Fields, 162(3):679-705, 2015. arXiv
  • Constantinos Daskalakis, Ilias Diakonikolas and Rocco A. Servedio: Learning Poisson Binomial Distributions.
    Algorithmica, 72(1):316-357, 2015. Special Issue on New Theoretical Challenges in Machine Learning. Invited. arXiv
  • Constantinos Daskalakis and Christos Papadimitriou: Approximate Nash Equilibria in Anonymous Games.
    Journal of Economic Theory, 156:207--245, 2015. pdf
  • Yang Cai and Constantinos Daskalakis: Extreme-Value Theorems for Optimal Multidimensional Pricing.
    Games and Economic Behavior, 92:266--305, 2015. Special Issue for STOC/FOCS/SODA 2011. Invited. arxiv
  • Constantinos Daskalakis, Alan Deckelbaum and Anthony Kim: Near-Optimal No-Regret Algorithms for Zero-sum Games.
    Games and Economic Behavior, 92:327-348, 2015. Special Issue for STOC/FOCS/SODA 2011. Invited. pdf
  • Constantinos Daskalakis, Ilias Diakonikolas and Rocco A. Servedio: Learning k-Modal Distributions via Testing.
    Theory of Computing, 10:535--570, 2014. arXiv
  • 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: Alignment-Free Phylogenetic Reconstruction: Sample Complexity via a Branching Process Analysis.
    Annals of Applied Probability, 23(2): 693--721, 2013. arxiv
  • Sanjeev Arora, Constantinos Daskalakis and David Steurer: Message-Passing Algorithms and Improved LP Decoding.
    IEEE Transactions on Information Theory, 58(12): 7260--7271, 2012. pdf
  • Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld and Elad Verbin: Sorting and Selection in Posets.
    SIAM Journal on Computing, 40(3): 597-622, 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): 872-893, 2011. arxiv
  • Constantinos Daskalakis, Alexandros G. Dimakis and Elchanan Mossel: Connectivity and Equilibrium in Random Games.
    Annals of Applied Probability, 21(3):987-1016, 2011. arxiv
  • 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(1-2):149-189, 2011. arxiv
  • Constantinos Daskalakis, Aranyak Mehta and Christos H. Papadimitriou: A Note on Approximate Nash Equilibria.
    Theoretical Computer Science, 410(17), 1581--1588, 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), 195--259, 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), 3565-3578, August 2008. arXiv

Expository Articles

  • Constantinos Daskalakis: Nash equilibria: Complexity, symmetries, and approximation.
    Computer Science Review 3(2): 87--100, 2009. pdf
  • Constantinos Daskalakis, Paul W. Goldberg and Christos H. Papadimitriou: The complexity of computing a Nash equilibrium.
    Communications of the ACM 52(2):89--97, 2009. pdf

Publications in Chronological Order

  • Yang Cai and Constantinos Daskalakis: Learning Multi-Item Auctions with (and without) Samples.
    Manuscript, 2017. arXiv
  • Constantinos Daskalakis, Nishanth Dikkala and Gautam Kamath: Testing Ising Models.
    Manuscript, 2017. arXiv
  • Constantinos Daskalakis, Nishanth Dikkala and Nick Gravin: Testing from One Sample: Is the casino really using a riffle shuffle?
    Manuscript, 2017. arXiv
  • Constantinos Daskalakis, Christos Tzamos and Manolis Zampetakis: A Converse to Banach's Fixed Point Theorem and its CLS Completeness.
    Manuscript, 2017. arXiv
  • 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 NIPS 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, Alan Deckelbaum and Christos Tzamos: Strong Duality for a Multiple-Good Monopolist.
    Econometrica, to appear. arXiv
  • 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 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
  • 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 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 Christos Papadimitriou: Sparse Covers for Sums of Indicators.
    Probability Theory and Related Fields, 162(3):679-705, 2015. arXiv
  • Constantinos Daskalakis and Christos Papadimitriou: Approximate Nash Equilibria in Anonymous Games.
    Journal of Economic Theory, 156:207--245, 2015. pdf
  • Jayadev Acharya, Constantinos Daskalakis and Gautam Kamath: Optimal Testing for Properties of Distributions.
    In the 29th Annual Conference on Neural Information Processing Systems (NIPS), NIPS 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, 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 Jayadev Acharya: Testing Poisson Binomial Distributions.
    In the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA 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 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, Alan Deckelbaum and Christos Tzamos: The Complexity of Optimal Mechanism Design.
    In the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA 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 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA 2014. arxiv
  • Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnel, Rocco Servedio and Li-Yang 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. 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
  • 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, 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 Multi-Dimensional 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 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.
  • 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
    Theory of Computing, 10:535--570, 2014. 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: 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, 21(3):987-1016, 2011. arxiv
  • 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(1-2):149-189, 2011. arxiv
  • Constantinos Daskalakis: On the Complexity of Approximating a Nash Equilibrium.
    In the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011.
    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
  • 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: Alignment-Free Phylogenetic Reconstruction.
    In the 14th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2010. pdf
    Annals of Applied Probability, 23(2): 693--721, 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): 3852--3874, 2012. journal version
  • 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
  • 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: 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, 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): 872-893, 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 Action-Graph Games.
    In the 20th Annual ACM-SIAM 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 ACM-SIAM Symposium On Discrete Algorithms, SODA 2009. arxiv
    SIAM Journal on Computing, 40(3): 597-622, 2011.
  • Constantinos Daskalakis: An Efficient PTAS for Two-Strategy 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
  • Constantinos Daskalakis and Christos H. Papadimitriou: Computing Equilibria in Anonymous Games.
    In the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. arXiv.
  • Constantinos Daskalakis, Aranyak Mehta and Christos H. Papadimitriou: Progress in Approximate Nash Equilibria.
    In the 8th ACM Conference on Electronic Commerce, EC 2007. pdf.
  • 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. arxiv
  • Constantinos Daskalakis, Alexandros G. Dimakis, Richard Karp and Martin Wainwright: Probabilistic Analysis of Linear Programming Decoding.
    In the 18th Annual ACM-SIAM Symposium On Discrete Algorithms, SODA 2007. arXiv
    Journal version in IEEE Transactions on Information Theory, 54(8), 3565-3578, August 2008. arxiv
  • C. Daskalakis, C. Hill, A. Jaffe, R. Mihaescu, E. Mossel and S. Rao: Maximal Accurate Forests From Distance Matrices.
    In the 10th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2006. pdf.
  • Constantinos Daskalakis, Alex Fabrikant and Christos Papadimitriou: The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games.
    In the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006. 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 Paper Award. pdf
  • Constantinos Daskalakis and Christos H. Papadimitriou: Three-Player Games Are Hard.
    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. 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.)
  • Constantinos Daskalakis, Elchanan Mossel and Sebastien Roch: Optimal Phylogenetic Reconstruction.
    In the 38th ACM Symposium on Theory of Computing, STOC 2006. arXiv
    Journal version in Probability Theory and Related Fields, 149(1-2):149-189, 2011.
  • Constantinos Daskalakis and Christos Papadimitriou: The Complexity of Games on Highly Regular Graphs.
    In the 13th Annual European Symposium on Algorithms, ESA 2005. pdf

List of Publications by Topic

Algorithmic Game Theory

 

Computational Biology

 

Learning, Statistics and Probability

 

Other Topics