Ali Vakilian

Research Interests

Algorithmic Foundations of Machine Learning and Data Science. In particular:

• Algorithms for Massive Data: streaming, sketching, and sublinear-time algorithms
• Algorithms & ML: learning-augmented algorithms, randomized numerical linear algebra
• Trustworthy ML: algorithmic fairness, learning with strategic agents

As well as combinatorial optimization and approximation algorithms.

• Oct 2027
  Invited talks at Theory Seminar Series at NYU, Johns Hopkins University, and Rutgers University.
• Sep 2026
  Joined Rutgers Business School as an Assistant Professor in the Department of Management Science and Information Systems.
• Jun 2026
  Invited talk at the Leveraging Data for Performance with Theoretical Guarantees tutorial at COLT 2026.
• Jun 2026
  Co-organizing the Machine Learning for Algorithms workshop at STOC 2026.
• Jun 2026
  Invited talk at the Learning-augmented Algorithms: Theory and Applications (LATA) workshop at SIGMETRICS 2026.
• Apr 2026
  Honored to receive an NSF CAREER Award. Grateful to the National Science Foundation for this support.
• Sep 2025
  Released a preliminary survey, Fair Clustering: Concepts, Methods, and Algorithms. I also maintain the Algorithmic Fair Clustering Repository. Feedback is welcome.
• Aug 2025
  Co-organized the Workshop on Local Algorithms (WOLA). (videos)
• Aug 2025
  Joined Virginia Tech as an Assistant Professor in the Department of Computer Science.
• May 2024
  Long-term participant in the Sublinear Algorithms program at the Simons Institute at Berkeley.
• May 2024
  “Learning-Based Graph Searching Problems” received the Outstanding Student Paper Highlight Award at AISTATS 2024.

Teaching & Mentorship

• Courses
  • TBA: Algorithmic Machine Learning (Rutgers, Fall 2026)
  • CS 6104: Algorithms for Big Data (Virginia Tech, Fall 2025)
  • TTIC 31150 / CMSC 31150: Mathematical Toolkit (TTIC / UChicago, Spring 2023)
• Virginia Tech: Rojin Rezvan (Postdoc; Oct 2025 – )
• Interns at TTIC: Amir Azarmehr (PhD at Northeastern; 2025), Madhusudhan Pittu (PhD at CMU; 2023), Erasmo Tani (PhD at UChicago; 2023)
• Fatima Fellows (see the Fatima Fellow program): Sèdjro Hotegni (MS at African Institute for Mathematical Sciences—Rwanda; 2022)

1. 2027
2. Approximating Minimum Spanning Trees in Metrics under Semi-Random Corruptions
   Aditya Anand, Anupam Gupta, Rajesh Jayaram, Euiwoong Lee, Ali Vakilian.
   SODA 2027
3. 2026
4. Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
   Yinhao Dong, Pan Peng, Ali Vakilian, Santhoshini Velusamy, Xiaoyang Xu.
   NeurIPS 2026
5. Graph-Based Nearest-Neighbor Search without the Spread
   Jeff Giliberti, Sariel Har-Peled, Jonas Sauer, Ali Vakilian.
   September 2026
6. A Configuration-LP Framework for Connected k-Median Clustering
   Kushagra Chatterjee, Rojin Rezvan, Ali Vakilian.
   APPROX 2026
7. Learning with Conflicts of Interest
   Nischal Aryal, Arash Termehchy, Ali Vakilian, Marianne Winslett.
   July 2026
8. An Optimal Algorithm for Stochastic Vertex Cover
   Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Cliff Stein, Miltiadis Stouras, Ola Svensson, Ali Vakilian.
   STOC 2026
9. A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering
   Sayan Bandyapadhyay, Eden Chlamtáč, Zachary Friggstad, Mahya Jamshidian, Yury Makarychev, Ali Vakilian.
   AISTATS 2026
10. Sublinear Metric Steiner Forest via Maximal Independent Set
    Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian.
    SODA 2026
11. 2025
12. Fair Clustering: Concepts, Methods, and Algorithms [fair-clustering repository]
    Ali Vakilian.
    September 2025 · preliminary version; feedback welcome.
13. Max-Cut with Multiple Cardinality Constraints
    Yury Makarychev, Madhusudhan Pittu, Ali Vakilian.
    APPROX 2025
14. Streaming Algorithms for Network Design
    Chandra Chekuri, Rhea Jain, Sepideh Mahabadi, Ali Vakilian.
    APPROX 2025
15. New and Improved Bounds for Markov Paging
    Chirag Pabbaraju, Ali Vakilian.
    ICALP 2025
16. Guessing Efficiently for Constrained Subspace Approximation
    Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Pittu, Ali Vakilian, David Woodruff.
    ICALP 2025
17. Minimax Group Fairness in Strategic Classification
    Emily Diana, Saeed Sharifi-Malvajerdi, Ali Vakilian.
    SaTML 2025
18. Learning-Augmented Streaming Algorithms for Approximating Max-Cut
    Yinhao Dong, Pan Peng, Ali Vakilian.
    ITCS 2025
19. Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
    Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian.
    ITCS 2025
20. 2024
21. Bayesian Strategic Classification
    Lee Cohen, Saeed Sharifi-Malvajerdi, Kevin Stangl, Ali Vakilian, Juba Ziani.
    NeurIPS 2024
22. On Socially Fair Low-Rank Approximation and Column Subset Selection
    Zhao Song, Ali Vakilian, David Woodruff, Samson Zhou.
    NeurIPS 2024
23. Streaming Algorithms for Connectivity Augmentation
    Ce Jin, Michael Kapralov, Sepideh Mahabadi, Ali Vakilian.
    ICALP 2024
24. Learning-Based Algorithms for Graph Searching Problems [code]
    Adela DePavia, Erasmo Tani, Ali Vakilian.
    AISTATS 2024; selected for Oral presentation Outstanding Student Paper Highlight Award (7 of 547 accepted papers)
25. Scalable Algorithms for Individual Preference Stable Clustering
    Ron Mosenzon, Ali Vakilian.
    AISTATS 2024
26. 2023
27. Constant Approximation for Individual Preference Stable Clustering
    Anders Aamand, Justin Chen, Allen Liu, Sandeep Silwal, Pattara Sukprasert, Ali Vakilian, Fred Zhang.
    NeurIPS 2023; selected for Spotlight presentation
28. Improved Frequency Estimation Algorithms with and without Predictions
    Anders Aamand, Justin Chen, Huy Nguyen, Sandeep Silwal, Ali Vakilian.
    NeurIPS 2023; selected for Spotlight presentation
29. Tight Bounds for Volumetric Spanners and Applications
    Aditya Bhaskara, Sepideh Mahabadi, Ali Vakilian.
    NeurIPS 2023
30. Approximating Red-Blue Set Cover
    Eden Chlamtáč, Yury Makarychev, Ali Vakilian.
    APPROX 2023
31. Sequential Strategic Screening
    Lee Cohen, Saeed Sharifi-Malvajerdi, Kevin Stangl, Ali Vakilian, Juba Ziani.
    ICML 2023
32. Approximation Algorithms for Fair Range Clustering
    Sèdjro Hotegni, Sepideh Mahabadi, Ali Vakilian.
    ICML 2023
33. Learning the Positions in CountSketch [code]
    Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David Woodruff.
    ICLR 2023; selected as Notable top-25% paper
34. 2022
35. Individual Preference Stability for Clustering [code]
    Saba Ahmadi, Pranjal Awasthi, Samir Khuller, Matthäus Kleindessner, Jamie Morgenstern, Pattara Sukprasert, Ali Vakilian.
    ICML 2022; selected for Long presentation
36. Faster Fundamental Graph Algorithms via Learned Predictions
    Justin Chen, Sandeep Silwal, Ali Vakilian, Fred Zhang.
    ICML 2022
37. Multi Stage Screening: Enforcing Fairness and Maximizing Efficiency in a Pre-Existing Pipeline
    Avrim Blum, Kevin Stangl, Ali Vakilian.
    FAccT 2022
38. Fair Representation Clustering with Several Protected Classes
    Zhen Dai, Yury Makarychev, Ali Vakilian.
    FAccT 2022
39. Improved Approximation Algorithms for Individually Fair Clustering
    Ali Vakilian, Mustafa Yalçıner.
    AISTATS 2022
40. Approximating Fair Clustering with Cascaded Norm Objectives
    Eden Chlamtáč, Yury Makarychev, Ali Vakilian.
    SODA 2022
41. 2021
42. Approximation Algorithms for Socially Fair Clustering
    Yury Makarychev, Ali Vakilian.
    COLT 2021
43. Learning Online Algorithms with Distributional Advice
    Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, Nikos Zarifis.
    ICML 2021
44. Node-weighted Network Design in Planar and Minor-closed Families of Graphs
    Chandra Chekuri, Alina Ene, Ali Vakilian.
    Transactions on Algorithms (TALG) 2021 · builds upon our ICALP 2012 paper; extends to element-connectivity requirements.
45. 2020
46. Individual Fairness for k-Clustering
    Sepideh Mahabadi, Ali Vakilian.
    ICML 2020
47. Improved Local Computation Algorithm for Set Cover via Sparsification
    Christoph Grunau, Slobodan Mitrović, Ronitt Rubinfeld, Ali Vakilian.
    SODA 2020
48. (Learned) Frequency Estimation Algorithms under Zipfian Distribution
    Anders Aamand, Piotr Indyk, Ali Vakilian.
    February 2020
49. 2019
50. Learning-Based Low-Rank Approximations
    Piotr Indyk, Ali Vakilian, Yang Yuan.
    NeurIPS 2019
51. Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
    Erik Demaine, Timothy Goodrich, Kyle Kloster, Brian Lavallee, Quanquan Liu, Blair Sullivan, Ali Vakilian, Andrew van der Poel.
    ESA 2019
52. Sample-Optimal Low-Rank Approximation of Distance Matrices
    Piotr Indyk, Ali Vakilian, Tal Wagner, David Woodruff.
    COLT 2019
53. Scalable Fair Clustering
    Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner.
    ICML 2019
54. Tight Trade-offs for Maximum k-Coverage Problem in the General Streaming Model
    Piotr Indyk, Ali Vakilian.
    PODS 2019
55. Learning-Based Frequency Estimation Algorithms [website] [code] [MIT News] [Forbes]
    Chen-Yu Hsu, Piotr Indyk, Dina Katabi, Ali Vakilian.
    ICLR 2019
56. Local Computation Algorithms for Spanners
    Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee.
    ITCS 2019
57. New Directions in Streaming Algorithms [DSpace@MIT]
    Ali Vakilian.
    Ph.D. Thesis, MIT EECS
58. 2018
59. Set Cover in Sub-linear Time
    Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee.
    SODA 2018
60. Approximation Algorithms for Nearly H-Minor-Free Graphs
    Erik Demaine, Quanquan Liu, Ali Vakilian.
    November 2018
61. Cost-Effective Conceptual Design Using Taxonomies
    Ali Vakilian, Yodsawalai Chodpathumwan, Arash Termehchy, Amir Nayyeri.
    VLDB Journal 2018
62. 2017
63. Fractional Set Cover in the Streaming Model
    Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, Anak Yodpinyanee.
    APPROX 2017
64. Cost-Effective Conceptual Design Over Taxonomies
    Ali Vakilian, Yodsawalai Chodpathumwan, Arash Termehchy, Amir Nayyeri.
    WebDB 2017
65. 2016
66. Towards Tight Bounds for the Streaming Set Cover Problem
    Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi, Ali Vakilian.
    PODS 2016
67. 2015
68. Cost-Effective Database Design For Information Extraction Applications
    Arash Termehchy, Ali Vakilian, Yodsawalai Chodpathumwan, Marianne Winslett.
    Transactions on Database Systems (TODS) 2015
69. 2014
70. On Streaming and Communication Complexity of The Set Cover Problem
    Erik Demaine, Piotr Indyk, Sepideh Mahabadi, Ali Vakilian.
    DISC 2014
71. Which Concepts are Worth Extracting?
    Arash Termehchy, Ali Vakilian, Yodsawalai Chodpathumwan, Marianne Winslett.
    SIGMOD 2014
72. Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements
    Alina Ene, Ali Vakilian.
    STOC 2014
73. 2013
74. Connected Domatic Packing in Node-capacitated Graphs
    Alina Ene, Nitish Korula, Ali Vakilian.
    July 2013
75. Node-Weighted Prize-Collecting Survivable Network Design Problems [IDEALS@UIUC]
    Ali Vakilian.
    M.S. Thesis, UIUC CS
76. 2012
77. Prize-collecting Survivable Network Design in Node-weighted Graphs
    Chandra Chekuri, Alina Ene, Ali Vakilian.
    APPROX 2012
78. Node-weighted Network Design in Planar and Minor-closed Families of Graphs
    Chandra Chekuri, Alina Ene, Ali Vakilian.
    ICALP 2012

• Streaming Algorithms for Connectivity Augmentation Problems
  • Simons Institute at Berkeley, Extroverted Sublinear Algorithms Workshop (6/20/24)
• Algorithms for Socially Fair Clustering: Min-Max Fairness to Cascaded Norms
  • MIT, A&C Seminar (12/6/23)
  • UW Seattle, Theory Seminar (11/13/23)
  • INFORMS Annual Meeting (10/15/23)
  • UT Austin, Theory Seminar (10/6/23)
  • Stanford, Algorithmic Fairness Seminar (10/2/23)
• Learning-Augmented Algorithms for Massive Data
  • INFORMS Annual Meeting (10/18/23)
• Tight Bounds for Volumetric Spanners in All Norms
  • Simons Institute at Berkeley, Sketching and Algorithm Design Workshop (10/11/23)
• Individual Preference Stability for Clustering
  • TRIPODS Postdoc Workshop (8/22/23)
  • Research at TTIC (2/24/23)
• Graph Algorithms with Learned Duals
  • “Scheduling” Seminar at Schloss Dagstuhl (2/9/23)

Copyright Notice

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.