Manolis Zampetakis

Welcome! I am a postdoc at the Department of Electrical Engineering and Computer Science at University of California at Berkeley working with Michael Jordan.

Before Berkeley I completed my PhD at the Department of Electrical Engineering and Computer Science at Massachusetts Institute of Technology (MIT) where I was very fortunate to be advised by Constantinos Daskalakis. My thesis can be found here.

My research interests include: Theoretical Machine Learning, Statistics, Optimization, Computational Complexity, Algorithmic Game Theory, and Sublinear Algorithms.

Email: mzampet [at) berkeley(dot]edu
CV: pdf

About

Before MIT, I was an undergraduate student at the Department of Electrical Engineering and Computer Science at National Technical University of Athens where I completed my Diploma Degree. During my time there, I was fortunate to work with Dimitris Fotakis on Mechanism Design with Verification and Scheduling Map-Reduce jobs.

During the Summer 2019 I joined as an intern the Microsoft Research Lab at New England where I worked with Vasilis Syrganis on Consistency of Random Forests.

During the Summer 2018 I joined as an intern the Scalable Machine Learning at Yahoo! Research at New York where I worked with Dimitris Fotakis, Robert Busa-Fukete and Balázs Szörényi on Learning and Testing Ranking Distributions.

During the Summer 2017 I joined as an intern the Algorithms and Optimization Group at Google Research at New York where I worked with Alessandro Epasto, Mohammad Mahdian and Vahab Mirrokni on Smooth Maximization with applications to Differential Privacy with applications to Mechanism Design.

From Fall 2018 to Spring 2020 my research was supported by Google PhD Fellowship.

Service

Research Papers & Manuscripts


    2021
  1. The Complexity of Constrained Min-Max Optimization
    with Constantinos Daskalakis and Stratis Skoulakis
    STOC 2021 ♦ 53rd Annual ACM Symposium on Theory of Computing
  2. A Topological Characterization of Modulo-p Arguments and Implications for
          Necklace Splitting
    with Aris Filos-Ratsikas, Alexandros Hollender and Katerina Sotiraki
    SODA 2021 ♦ 32nd ACM-SIAM Symposium on Discrete Algorithms

  3. 2020
    Ph.D. Thesis ♦ Statistics in High Dimensions without IID Samples:
                              Truncated Statistics and Minimax Optimization
  4. Constant-Expansion Suffices for Compressed Sensing with Generative Priors
    with Constantinos Daskalakis and Dhruv Rohatgi
    NeurIPS 2020 ♦ 34th Conference on Neural Information Processing Systems Spotlight Presentation
  5. Optimal Approximation - Smoothness Tradeoffs for Soft-Max Functions
    with Alessandro Epasto, Mohammad Mahdian and Vahab Mirrokni
    NeurIPS 2020 ♦ 34th Conference on Neural Information Processing Systems Spotlight Presentation
  6. Truncated Linear Regression in High Dimensions
    with Constantinos Daskalakis and Dhruv Rohatgi
    NeurIPS 2020 ♦ 34th Conference on Neural Information Processing Systems
  7. Estimation and Inference with Trees and Forests in High Dimensions
    with Vasilis Syrganis
    COLT 2020 ♦ 33rd Annual Conference on Learning Theory
  8. More Revenue from Two Samples via Factor Revealing SDPs
    with Constantinos Daskalakis
    EC 2020 ♦ 21st ACM Conference on Economics and Computation
  9. Consensus-Halving: Does it Ever Get Easier?
    with Aris Filos-Ratsikas, Alexandros Hollender and Katerina Sotiraki
    EC 2020 ♦ 21st ACM Conference on Economics and Computation
  10. On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem
    with Mika Göös, Pritish Kamath and Katerina Sotiraki
    CCC 2020 ♦ 35th Computational Complexity Conference
  11. A Theoretical and Practical Framework for Regression and Classification from
          Truncated Samples
    with Costantinos Daskalakis, Andrew Ilyas
    AISTATS 2020 ♦ 23rd International Conference on Artificial Intelligence and Statistics

  12. 2019
  13. Efficient Truncated Statistics with Unknown Truncation
    with Vasilis Kontonis, and Christos Tzamos
    FOCS 2019 ♦ 60th Annual IEEE Symposium on Foundations of Computer Science
  14. Computationally and Statistically Efficient Truncated Regression
    with Constantinos Daskalakis, Themis Gouleakis and Christos Tzamos
    COLT 2019 ♦ 32nd Conference on Learning Theory
  15. Optimal Learning of Mallows Block Model
    with Róbert Busa-Fekete, Dimitris Fotakis and Balázs Szörényi
    COLT 2019 ♦ 32nd Conference on Learning Theory

  16. 2018
  17. Efficient Statistics, in High Dimensions, from Truncated Samples
    with Constantinos Daskalakis, Themis Gouleakis and Christos Tzamos
    FOCS 2018 ♦ 59th Annual IEEE Symposium on Foundations of Computer Science
  18. PPP-completeness with Connections to Cryptography
    with Katerina Sotiraki and Giorgos Zirdelis
    FOCS 2018 ♦ 59th Annual IEEE Symposium on Foundations of Computer Science
  19.   Certified Computation from Unreliable Datasets
    with Themis Gouleakis and Christos Tzamos
    COLT 2018 ♦ 31th Conference on Learning Theory
  20.   A Converse to Banach's Fixed Point Theorem and its CLS Completeness
    with Constantinos Daskalakis and Christos Tzamos
    STOC 2018 ♦ 50th Annual ACM Symposium on the Theory of Computing
  21.   Bootstrapping EM via Power EM and Convergence in the Naive Bayes Model
    with Constantinos Daskalakis and Christos Tzamos
    AISTATS 2018 ♦ 21st International Conference on Artificial Intelligence and Statistics

  22. 2017
  23.   Ten Steps of EM Suffice for Mixtures of Two Gaussians
  24.   Faster Sublinear Algorithms using Conditional Sampling
    with Themis Gouleakis and Christos Tzamos
    SODA 2017 ♦ 28th ACM-SIAM Symposium on Discrete Algorithms

  25. 2013 - 2016
  26.   Mechanism Design with Selective Verification
    with Dimitris Fotakis and Christos Tzamos
    EC 2016 ♦ 17th ACM Economics and Computation
  27.   Efficient Money Burning in General Domains
    with Dimitris Fotakis , Dimitris Tsipras and Christos Tzamos
    SAGT 2015 ♦ 8th International Symposium on Algorithmic Game Theory Special Issue
  28.   Scheduling MapReduce Jobs and Data Shuffle on Unrelated Processors
    with Dimitris Fotakis , Ioannis Milis , Orestis Papadigenopoulos and Giorgos Zois
    SEA 2015 ♦ 14th International Symposium on Experimental Algorithms
    Preliminary version: EDBT/ICDT Workshop on Algorithms for Map Reduce and Beyond, 2014.
  29.   Truthfulness Flooded Domains and the Power of Verification for Mechanism Design
    with Dimitris Fotakis
    WINE 2013 ♦ 9th Conference on Web and Internet Economics Special Issue