Constantinos Daskalakis

    Associate Professor, EECS, MIT

[Teaching]

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)

Research Interests

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

Awards

Here is a list of awards.

Publications

Journal Publications

Expository Articles

Recent (2008+) Publications in Chronological Order

  • Constantinos Daskalakis, Christos Tzamos and Manolis Zampetakis: Ten Steps of EM Suffice for Mixtures of Two Gaussians.
    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.
    Working Paper, 2016. arXiv
  • Constantinos Daskalakis, Nishanth Dikkala and Gautam Kamath: Testing Ising Models.
    Working Paper, 2016. 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

Complete List of Publications by Topic

Algorithmic Game Theory

 

Computational Biology

 

Learning, Testing and Applied Probability

 

Other Topics