Christos Tzamos

I study Computer Science in the Theory of Computation group at MIT where I am advised by Constantinos Daskalakis.

My research interests include Algorithmic Game Theory, Learning Theory as well as the Design, Analysis and Theory of Algorithms.

About

I joined the graduate program of MIT on September 2011 in the Theory of Computation group at CSAIL. My PhD advisor is Costis Daskalakis and I enjoy working with him on a wide range of problems from auction theory to learning theory.

I grew up in Athens, Greece where I also had my undergraduate studies at the National Technical University of Athens (Sept. 2006 - June 2011). During my time there, I had the opportunity to work with my advisor Dimitris Fotakis on different problems in mechanism design without money.

I spent the summer of 2014 as a research intern at Yahoo! Labs, Sunnyvale working with Chris Wilkens on multiple research and practical questions regarding online ad auctions. I also interned for Google, Cambridge in the mobile search team during summer 2012.

Research

I am interested in Algorithmic Game Theory, Learning Theory as well as in the Design, Analysis and Theory of Algorithms.

Journal Articles

1. “Strong Duality for a Multiple-Good Monopolist”
   with C. Daskalakis, and A. Deckelbaum
   
   Econometrica 85(3): 735-767 (2017)
2. “Efficient Money Burning in General Domains”
   with D. Fotakis, D. Tsipras, and E. Zampetakis
   
   Theory of Computing Systems. Special Issue for SAGT 2015. Invited.
3. “Strategyproof Facility Location for Concave Cost Functions”
   with D. Fotakis
   
   Algorithmica 76(1): 143-167 (2016)
4. “On the Power of Deterministic Mechanisms for Facility Location Games”
   with D. Fotakis
   
   ACM Transactions on Economics and Computation 2(4): 15:1-15:37 (2014)
5. “Winner-Imposing Strategyproof Mechanisms for Multiple Facility Location Games”
   with D. Fotakis
   
   Theoretical Computer Science 472: 90-103 (2013)

Conference Proceedings

1. “Ten Steps of EM Suffice for Mixtures of Two Gaussians”
   with C. Daskalakis, and E. Zampetakis
   
   in the 30th Annual Conference on Learning Theory, COLT 2017
2. “Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms”
   with A. Backurs
   
   in the 34th International Conference on Machine Learning, ICML 2017
3. “Faster Sublinear Algorithms via Conditional Sampling”
   with T. Gouleakis, and E. Zampetakis
   
   in the 28th ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
4. “Does Information Revelation Improve Revenue?”
   with C. Daskalakis, and C. Papadimitriou
   
   in the 17th ACM Conference on Economics and Computation, EC 2016
5. “Mechanism Design with Selective Verification”
   with D. Fotakis, and E. Zampetakis
   
   in the 17th ACM Conference on Economics and Computation, EC 2016
6. “Tight Hardness Results for Maximum Weight Rectangles”
   with A. Backurs, and N. Dikkala
   
   in the 43rd Int'l Colloquium on Automata, Languages and Programming, ICALP 2016
7. “Anonymous Auctions Maximizing Revenue”
   with C. Wilkens
   
   in the 12th Workshop on Internet & Network Economics, WINE 2016
8. “A Size-Free CLT for Poisson Multinomials and its Applications”
   with C. Daskalakis, A. De, and G. Kamath
   
   in the 48th ACM Symposium on Theory of Computing, STOC 2016
9. “On the Structure, Covering and Learning of Poisson Multinomial Distributions”
   with C. Daskalakis, and G. Kamath
   
   in the 56th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2015
10. “Strong Duality for a Multiple-Good Monopolist”
    with C. Daskalakis, and A. Deckelbaum
    
    in the 16th ACM Conference on Economics and Computation, EC 2015
11. “Efficient Money Burning in General Domains”
    with D. Fotakis, D. Tsipras, and E. Zampetakis
    
    in the 8th International Symposium on Algorithmic Game Theory, SAGT 2015
12. “The Complexity of Optimal Mechanism Design”
    with C. Daskalakis, and A. Deckelbaum
    
    in the 25th ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
13. “Mechanism Design via Optimal Transport”
    with C. Daskalakis, and A. Deckelbaum
    
    in the 14th ACM Conference on Economics and Computation, EC 2013
    ★ Best Paper and Best Student Paper Award
14. “Strategyproof Facility Location for Concave Cost Functions”
    with D. Fotakis
    
    in the 14th ACM Conference on Economics and Computation, EC 2013
15. “On the Power of Deterministic Mechanisms for Facility Location Games”
    with D. Fotakis
    
    in the 40th Int'l Colloquium on Automata, Languages and Programming, ICALP 2013
16. “Optimal Pricing is Hard”
    with C. Daskalakis, and A. Deckelbaum
    
    in the 8th Workshop on Internet & Network Economics, WINE 2012
17. “Winner-Imposing Strategyproof Mechanisms for Multiple Facility Location Games”
    with D. Fotakis
    
    in the 6th Workshop on Internet & Network Economics, WINE 2010

Working Papers

1. “Optimal Seat Pricing With Multiple Classes & Why Economy Seats Feel so Small”
   with I. Stamatopoulos
   
   

Awards and Honors

• Simons Award for Graduate Students in Theoretical Computer Science (2014-2016)
• Best Paper and Best Student Paper Award in the 14th Conference on Economics and Computation (2013)
• Kanellakis Fellowship for EECS students of MIT (2011-2012)
• Programming/Mathematics competitions:
  • World Finalist in ACM International Collegiate Programming Contest (2012)
  • Silver Medal in International Mathematics Competition for University Students (2010)
  • First Place in Norwegian IDI Open Programming Competition (2009)
  • Silver Medal in International Olympiad in Informatics (2006)
  • Gold Medal in Balkan Olympiad in Informatics (2006)

Miscellaneous

• Revenue-optimal mechanisms for Beta distributed items.
• The EM algorithm for Naive-Bayes.
• A collection of hard riddles and puzzles.
• A script generating random passwords.