Vaggos (Evangelos) Chatziafratis

vaggos at cs.stanford.edu OR vaggos at ucsc.edu
(check also my Google Scholar)

As of July 2021, I've joined UC Santa Cruz as an Assistant Professor in the CSE department. During the academic year 2021-2022 (on leave), I was a postdoc at Northwestern mentored by Samir Khuller, Aravindan Vijayaraghavan and Kostya Makarychev. In January 2022, I joined MIT/Northeastern as a FODSI fellow.

Prior to this, I had spent a wonderful year at Google Research in New York hosted by Mohammad Mahdian and Vahab Mirrokni. I received my PhD in Computer Science from Stanford University, where I had the privilege to be advised by Tim Roughgarden and co-advised by Moses Charikar. My thesis was on Hierarchical Clustering.

Prior to Stanford, I received my Diploma in EECS from the National Technical University of Athens, Greece.


Recent News/Talks

  • January'23: Paper accepted to ICLR as an oral presentation (top 5%).
  • January'23: Teaching CSE102: Introduction to Analysis of Algorithms.
  • September'22: Teaching CSE290A: Topics in Algorithms (Clustering, SDPs, Hierarchical Clustering, Hardness).
  • April'22: Invited talk at IDEAL Clustering Workshop, on Hierarchical Clustering (Video) .
  • March'22: Talk at Piotr Indyk's group at MIT, on Hierarchical Clustering.
  • November'21: Talk at Northwestern CS Seminar, on Deep Learning through the lens of Dynamical Systems.
  • October'21: Talk at UC Irvine CS Seminar, on Hierarchical Clustering.
  • October'21: Talk at Northwestern CS Seminar, on Hierarchical Clustering.
  • July'21: Joined UC Santa Cruz. If you like my research, apply to our MS/PhD program.

Older News/Talks

  • October'20: Invited talk at Harvard's CS for Mathematicians seminar.
  • October'20: Invited lecture based on ICLR'20 and ICML'20 at Northeastern's Special Topics in Deep Learning class.
  • October'20: Presenting recent work on Aggregating Inconsistent Information at the Michigan-Purdue Theory seminar.
  • September'20: New paper at NeurIPS'20 on Hyperbolic Hierarchical Clustering.
  • July'20: Talk at Stanford's Theory/ML groups for our ICLR'20 and ICML'20 papers on depth/width tradeoffs.
  • July'20: Started at Google Research New York as a Visiting Faculty Researcher in the market algorithms group.
  • January'20: Talk at Google Zurich (host: Silvio Lattanzi) on DNN's depth separation results via dynamical systems.
  • September'19: PapaFest is coming to Columbia for us to celebrate Christos Papadimitriou 70th birthday.
  • June'19: Visit to Phoenix, Arizona for FCRC and to present our COLT paper.
  • April'19: AISTATS and visit to Tokyo Institute of Technology to present our paper to their AI & Web Mining lab.
  • March'19: Excited to present our work at Columbia's Theory Seminar.
  • March'19: Excited to present our work at Corelab's Theory Seminar, NTUA, Greece.
  • February/March'19: Visiting Ioannis Panageas at Singapore's SUTD to present our recent results.
  • February'19: Talk on Hierarchical Clustering in Facebook's Computer Vision group, Menlo Park.
  • February'19: Talk on the Computational Power of Online Gradient Descent in Stanford's Theory and ML groups.
  • Summer'19: Joined Google NY for a summer internship under Mohammad Mahdian and Vahab Mirrokni.
  • December'18: Talk on Hierarchical Clustering at Google Zurich and ETH Zurich algorithms seminar.

Ph.D. Dissertation

Hierarchical Clustering with Global Objectives: Approximation Algorithms and Hardness Results
Evangelos (Vaggos) Chatziafratis, Stanford University, June 2020
Committee: Tim Roughgarden (Adviser), Moses Charikar (Co-Adviser), Li-Yang Tan, Greg Valiant, Jan Vondrak (Chair)

Working Papers

  1. Learning on Trees with Ordinal Constraints.
    Vaggos Chatziafratis, Tasos Sidiropoulos.
    work in progress.
  2. Hierarchical Clustering with Geometric Diversity via Greedy Volume Minimization.
    Vaggos Chatziafratis, Insu Han.
    work in progress.

All Publications (also see my Google Scholar)

  1. Embedding Dimension of Contrastive Learning and k-Nearest Neighbors.
    Dmitrii Avdiukhin, Vaggos Chatziafratis, Orr Fischer, Grigory Yaroslavtsev.
    NeurIPS 2024, 38th Conference on Neural Information Processing Systems, Vancouver, Canada, December 2024.
  2. From Large to Small Datasets: Size Generalization for Clustering Algorithm Selection.
    Vaggos Chatziafratis, Ishani Karmarkar, Ellen Vitercik.
    arxiv, submitted, 2024.
  3. Approximation Scheme for Weighted Metric Clustering via Sherali-Adams.
    Dmitrii Avdiukhin, Vaggos Chatziafratis, Konstantin Makarychev, Grigory Yaroslavtsev.
    AAAI 2024 (Oral talk), 38th AAAI Conference on Artificial Intelligence, Vancouver, Canada, February 2024.
  4. Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors.
    Vaggos Chatziafratis, Piotr Indyk.
    SOSA@SODA 2024, 7th ACM-SIAM Symposium on Simplicity in Algorithms, Alexandria, Virginia, January 2024.
  5. Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant.
    Vaggos Chatziafratis, Konstantin Makarychev.
    FOCS 2023, 64th IEEE Symposium on Foundations of Computer Science, Santa Cruz, California, November 2023.
  6. Efficiently Computing Nash Equilibria in Adversarial Team Markov Games.
    Fivos Kalogiannis, Ioannis Anagnostides, Ioannis Panageas, Manolis Vlatakis, Vaggos Chatziafratis, Stelios Stavroulakis.
    ICLR 2023 (Oral talk), 11th International Conference on Learning Representations, Kigali, Rwanda, May 2023.
  7. On Scrambling Phenomena for Randomly Initialized Recurrent Networks.
    Vaggos Chatziafratis, Ioannis Panageas, Clayton Sanford, Stelios Andrew Stavroulakis.
    NeurIPS 2022, 36th Conference on Neural Information Processing Systems, New Orleans, Louisiana, December 2022.
  8. Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds.
    Sepehr Assadi, Vaggos Chatziafratis, Jakub Łącki, Vahab Mirrokni, Chen Wang.
    COLT 2022, 35th Annual Conference on Learning Theory, London, UK, July 2022.
  9. Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theorem.
    Clayton Sanford, Vaggos Chatziafratis.
    AISTATS 2022, 25th International Conference on Artificial Intelligence and Statistics, virtual.
  10. Adversarially Robust Low Dimensional Representations.
    Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, Aravindan Vijayaraghavan.
    COLT 2021, 34th Annual Conference on Learning Theory, Boulder, Colorado, August 2021.
  11. Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT.
    Vaggos Chatziafratis, Mohammad Mahdian, Sara Ahmadian.
    AISTATS 2021, 24th International Conference on Artificial Intelligence and Statistics, virtual.
  12. Hierarchical Clustering via Sketches and Hierarchical Correlation Clustering.
    Danny Vainstein*, Vaggos Chatziafratis*, Gui Citovski, Anand Rajagopalan, Mohammad Mahdian, Yossi Azar.
    AISTATS 2021, 24th International Conference on Artificial Intelligence and Statistics, virtual.
  13. From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering.
    Ines Chami, Vaggos Chatziafratis, Albert Gu, Christopher Re.
    NeurIPS 2020, 34th Conference on Neural Information Processing Systems, virtual, December 2020.
  14. Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering.
    Vaggos Chatziafratis, Neha Gupta, Euiwoong Lee.
    IPL 2020, (Journal), Information Processing Letters (minor revision).
  15. Better Depth-Width Trade-offs for Neural Networks through the lens of Dynamical Systems. [15min ICML Talk]
    Vaggos Chatziafratis, Sai Ganesh Nagarajan, Ioannis Panageas.
    ICML 2020, 37th International Conference on Machine Learning, virtual, July 2020.
  16. Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection.
    Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto, Euiwoong Lee, Mohammad Mahdian, Konstantin Makarychev, Grigory Yaroslavtsev.
    AISTATS 2020, 23rd International Conference on Artificial Intelligence and Statistics, Palermo, Italy, June 2020.
  17. Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem. [5min ICLR Spotlight]
    Vaggos Chatziafratis, Sai Ganesh Nagarajan, Ioannis Panageas, Xiao Wang.
    ICLR 2020 (Spotlight talk), 8th International Conference on Learning Representations, Addis Ababa, Ethiopia, April 2020.
  18. Bilu-Linial stability, Certified Algorithms and the Independent Set problem.
    Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, Chen Dan.
    ESA 2019, 27th European Symposium on Algorithms, Munich, Germany, September 2019.
  19. On the Computational Power of Online Gradient Descent.
    Vaggos Chatziafratis, Tim Roughgarden, Joshua R. Wang.
    COLT 2019, 32nd Annual Conference on Learning Theory, Phoenix, Arizona, June 2019.
  20. Hierarchical Clustering for Euclidean Data.
    Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev.
    AISTATS 2019, 22nd International Conference on Artificial Intelligence and Statistics, Naha, Okinawa, Japan, April 2019.
  21. Hierarchical Clustering better than Average-Linkage.
    Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh.
    SODA 2019, 30th ACM-SIAM Symposium on Discrete Algorithms, San Diego, California, January 2019.
  22. Hierarchical Clustering with Structural Constraints. [10min ICML Talk]
    Vaggos Chatziafratis, Rad Niazadeh, Moses Charikar.
    ICML 2018, 35th International Conference on Machine Learning, Stockholm, Sweden, July 2018.
  23. Attack vulnerability of power systems under an equal load redistribution model.
    Talha Cihad Gulcu, Vaggos Chatziafratis, Yingrui Zhang, and Osman Yağan.
    ToN 2018 (Journal), IEEE/ACM Transactions on Networking, 26(3): 1306-1319, June 2018.
  24. Stability and Recovery for Independence Systems.
    Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrák.
    ESA 2017, 25th European Symposium on Algorithms, Vienna, Austria, September 2017.
  25. Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics.
    Moses Charikar, Vaggos Chatziafratis.
    SODA 2017, 28th ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, January 2017.
  26. On the robustness of power systems: optimal load-capacity distributions and hardness of attacking.
    Vaggos Chatziafratis, Yingrui Zhang, Osman Yağan.
    ITA 2016 (Invited), 11th Information Theory and Applications Workshop, San Diego, California, February 2016.

Service

  • Program Committee: AAAI 2021, COLT 2021
  • External Reviewer (Journals): JACM, JMLR, Journal of Computational Geometry, Theoretical Computer Science
  • External Reviewer (Conferences): ICML, NeurIPS, COLT, ICLR, AISTATS, SODA, FOCS, ESA, STACS

Professional Experience

Teaching Experience

Miscellaneous

  • Leadership at Stanford:
    • President of HELLAS (Hellenic Association at Stanford): Organizing Stanford-wide cultural events.
    • Stanford GSPB (Graduate Student Programming Board): Organizing social events for the grad community.
  • Arts:
    • Music: Diploma in Classical Piano and Music Theory, Greece. Student of Kumaran Arul at Stanford's Music Department.
    • Theater: Playback Theater under Omer Reingold.
  • Volunteering:
    • Mentoring Greek students through Global Prep by raising awareness and providing information about grad school in the US.
    • Organizing annual Educational Trip with the collaboration of MIT, Princeton, UC Berkeley, UC San Diego, Georgia Tech.
    • National Hellenic Student Association: NHSA's Executive Board Member.