Vaggos (Evangelos) Chatziafratis

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. From Large to Small Datasets: Size Generalization for Clustering Algorithm Selection.
   Vaggos Chatziafratis, Ishani Karmarkar, Ellen Vitercik.
   arxiv, submitted, 2024.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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.
12. 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.
13. Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering.
    Vaggos Chatziafratis, Neha Gupta, Euiwoong Lee.
    IPL 2020, (Journal), Information Processing Letters (minor revision).
14. 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.
15. 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.
16. 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.
17. 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.
18. 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.
19. 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.
20. 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.
21. 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.
22. 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.
23. Stability and Recovery for Independence Systems.
    Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrák.
    ESA 2017, 25th European Symposium on Algorithms, Vienna, Austria, September 2017.
24. 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.
25. 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

• Summer 2019: Google NY Research Internship in Algorithms under Mohammad Mahdian and Vahab Mirrokni.
• Summer 2018: Facebook Research Internship in Core Data Science under Julian Mestre and Nicolas Stier.
• Summer 2017: Research Assistant at Stanford University under Greg Valiant.
• Summer 2016: Research Internship at École Polytechnique Federal de Lausanne (EPFL), Switzerland.
• Summer 2015: Software Engineering Internship at CERN in Switzerland.
• Winter 2014: Software Engineering Internship at Lappeenranta University of Technology, Finland.

Teaching Experience

• Winter 2018: Teaching Assistant for CS161: Algorithms and Complexity under Leo Guibas.
• Fall 2017: Teaching Assistant for CS265: Randomized Algorithms and Probabilistic Analysis under Greg Valiant.
• Spring 2017: Teaching Assistant for CS168: Modern Algorithmic Toolbox under Tim Roughgarden and Greg Valiant.
• Fall 2016: Teaching Assistant for CS269I: Incentives in Computer Science under Tim Roughgarden.

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.