Ali Vakilian

I am an Assistant Professor in the Department of Computer Science at Virginia Tech. CS @ VTech. Before joining VTech, I was a Research Assistant Professor at Toyota Technological Institute at Chicago (TTIC). TTIC.

• Ph.D., EECS at MIT
  Advisors: Erik Demaine and Piotr Indyk
  
• M.S., CS at University of Illinois at Urbana-Champaign UIUC
  Advisor: Chandra Chekuri
  
• B.S., CE at Sharif UniversityCE at Sharif U.

vakilian [at] vt [dot] edu

Research Interests

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

• Algorithms for Massive Data: Streaming, Sketching and Sublinear Time Algorithms
• Algorithms for ML: Learning-Augmented Algorithms, Randomized Numerical Linear Algebra
• Trustworthy ML: Algorithmic Fairness, Learning with Strategic Agents

as well as, Combinatorial Optimization & Approximation Algorithms.

Teaching & Mentorship

• Courses:
  • 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 25 — )
• Interns at TTIC: Amir Azarmehr (PhD at Northeastern; 2025), Madhusudhan Pittu (PhD at CMU; 2023), Erasmo Tani (PhD at UChicago; 2023)
• Fatima Fellows (check the Fatima Fellow program): Sèdjro Hotegni (MS at African Institute for Mathematical Sciences—Rwanda; 2022)

Publications

• 2026
• Sublinear Metric Steiner Forest via Maximal Independent Set
  Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian.
  SODA 2026
• 2025
• Fair Clustering: Concepts, Methods, and Algorithms [fair clustering repository]
  Ali Vakilian.
  September 2025
  As this is a preliminary version, any feedback or comments are welcome.
• A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering
  Sayan Bandyapadhyay, Eden Chlamtáč, Zachary Friggstad, Mahya Jamshidian, Yury Makarychev, Ali Vakilian.
  February 2025
• Max-Cut with Multiple Cardinality Constraints
  Yury Makarychev, Madhusudhan Pittu, Ali Vakilian.
  APPROX 2025
• Streaming Algorithms for Network Design
  Chandra Chekuri, Rhea Jain, Sepideh Mahabadi, Ali Vakilian.
  APPROX 2025
• New and Improved Bounds for Markov Paging
  Chirag Pabbaraju, Ali Vakilian.
  ICALP 2025
• Guessing Efficiently for Constrained Subspace Approximation
  Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Pittu, Ali Vakilian, David Woodruff.
  ICALP 2025
• Minimax Group Fairness in Strategic Classification
  Emily Diana, Saeed Sharifi-Malvajerdi, Ali Vakilian.
  SaTML 2025
• Learning-Augmented Streaming Algorithms for Approximating Max-Cut
  Yinhao Dong, Pan Peng, Ali Vakilian.
  ITCS 2025
• Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
  Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian.
  ITCS 2025
• 2024
• Bayesian Strategic Classification
  Lee Cohen, Saeed Sharifi-Malvajerdi, Kevin Stangl, Ali Vakilian, Juba Ziani.
  NeurIPS 2024
• On Socially Fair Low-Rank Approximation and Column Subset Selection
  Zhao Song, Ali Vakilian, David Woodruff, Samson Zhou.
  NeurIPS 2024
• Streaming Algorithms for Connectivity Augmentation
  Ce Jin, Michael Kapralov, Sepideh Mahabadi, Ali Vakilian.
  ICALP 2024
• Learning-Based Algorithms for Graph Searching Problems [code]
  Adela DePavia, Erasmo Tani, Ali Vakilian.
  AISTATS 2024; selected for Oral presentation
  Recipient of outstanding student paper highlight award (awarded to 7 out of 547 accepted papers)
• Scalable Algorithms for Individual Preference Stable Clustering
  Ron Mosenzon, Ali Vakilian.
  AISTATS 2024
• 2023
• 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
• Improved Frequency Estimation Algorithms with and without Predictions
  Anders Aamand, Justin Chen, Huy Nguyen, Sandeep Silwal, Ali Vakilian.
  NeurIPS 2023; selected for Spotlight presentation
• Tight Bounds for Volumetric Spanners and Applications
  Aditya Bhaskara, Sepideh Mahabadi, Ali Vakilian.
  NeurIPS 2023
• Approximating Red-Blue Set Cover
  Eden Chlamtáč, Yury Makarychev, Ali Vakilian.
  APPROX 2023
• Sequential Strategic Screening
  Lee Cohen, Saeed Sharifi-Malvajerdi, Kevin Stangl, Ali Vakilian, Juba Ziani.
  ICML 2023
• Approximation Algorithms for Fair Range Clustering
  Sèdjro Hotegni, Sepideh Mahabadi, Ali Vakilian.
  ICML 2023
• Learning the Positions in CountSketch [code]
  Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David Woodruff.
  ICLR 2023; selected as Notable-top-25% paper
• 2022
• 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
• Faster Fundamental Graph Algorithms via Learned Predictions
  Justin Chen, Sandeep Silwal, Ali Vakilian, Fred Zhang.
  ICML 2022
• Multi Stage Screening: Enforcing Fairness and Maximizing Efficiency in a Pre-Existing Pipeline
  Avrim Blum, Kevin Stangl, Ali Vakilian.
  FAccT 2022
• Fair Representation Clustering with Several Protected Classes
  Zhen Dai, Yury Makarychev, Ali Vakilian.
  FAccT 2022
• Improved Approximation Algorithms for Individually Fair Clustering
  Ali Vakilian, Mustafa Yalçıner.
  AISTATS 2022
• Approximating Fair Clustering with Cascaded Norm Objectives
  Eden Chlamtáč, Yury Makarychev, Ali Vakilian.
  SODA 2022
• 2021
• Approximation Algorithms for Socially Fair Clustering
  Yury Makarychev, Ali Vakilian.
  COLT 2021
• Learning Online Algorithms with Distributional Advice
  Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, Nikos Zarifis.
  ICML 2021
• 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 and extends to the element-connectivity requirements.
• 2020
• Individual Fairness for k-Clustering
  Sepideh Mahabadi, Ali Vakilian.
  ICML 2020
• Improved Local Computation Algorithm for Set Cover via Sparsification
  Christoph Grunau, Slobodan Mitrović, Ronitt Rubinfeld, Ali Vakilian.
  SODA 2020
• (Learned) Frequency Estimation Algorithms under Zipfian Distribution
  Anders Aamand, Piotr Indyk, Ali Vakilian.
  February 2020.
• 2019
• Learning-Based Low-Rank Approximations
  Piotr Indyk, Ali Vakilian, Yang Yuan.
  NeurIPS 2019
• 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
• Sample-Optimal Low-Rank Approximation of Distance Matrices
  Piotr Indyk, Ali Vakilian, Tal Wagner, David Woodruff.
  COLT 2019
• Scalable Fair Clustering
  Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner.
  ICML 2019
• Tight Trade-offs for Maximum k-Coverage Problem in the General Streaming Model
  Piotr Indyk, Ali Vakilian.
  PODS 2019
• Learning-Based Frequency Estimation Algorithms [website] [code] [MIT News] [Forbes]
  Chen-Yu Hsu, Piotr Indyk, Dina Katabi, Ali Vakilian.
  ICLR 2019
• Local Computation Algorithms for Spanners
  Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee.
  ITCS 2019
• New Directions in Streaming Algorithms [DSpace@MIT]
  Ph.D. Thesis, MIT EECS
• 2018
• Set Cover in Sub-linear Time
  Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee.
  SODA 2018
• Approximation Algorithms for Nearly H-Minor-Free Graphs
  Erik Demaine, Quanquan Liu, Ali Vakilian. November 2018.
• Cost-Effective Conceptual Design Using Taxonomies
  Ali Vakilian, Yodsawalai Chodpathumwan, Arash Termehchy, Amir Nayyeri.
  VLDB Journal 2018
• 2017
• Fractional Set Cover in the Streaming Model
  Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, Anak Yodpinyanee.
  APPROX 2017
• Cost-Effective Conceptual Design Over Taxonomies
  Ali Vakilian, Yodsawalai Chodpathumwan, Arash Termehchy, Amir Nayyeri.
  WebDB 2017
• 2016
• Towards Tight Bounds for the Streaming Set Cover Problem
  Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi, Ali Vakilian.
  PODS 2016
• 2015
• Cost-Effective Database Design For Information Extraction Applications
  Arash Termehchy, Ali Vakilian, Yodsawalai Chodpathumwan, Marianne Winslett.
  Transactions on Database Systems (TODS) 2015
• 2014
• On Streaming and Communication Complexity of The Set Cover Problem
  Erik Demaine, Piotr Indyk, Sepideh Mahabadi, Ali Vakilian.
  DISC 2014
• Which Concepts are Worth Extracting?
  Arash Termehchy, Ali Vakilian, Yodsawalai Chodpathumwan, Marianne Winslett.
  SIGMOD 2014
• Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements
  Alina Ene, Ali Vakilian.
  STOC 2014
• 2013
• Connected Domatic Packing in Node-capacitated Graphs
  Alina Ene, Nitish Korula, Ali Vakilian.
  July 2013
• Node-Weighted Prize-Collecting Survivable Network Design Problems [IDEALS@UIUC]
  M.S. Thesis, UIUC CS
• 2012
• Prize-collecting Survivable Network Design in Node-weighted Graphs
  Chandra Chekuri, Alina Ene, Ali Vakilian.
  APPROX 2012
• Node-weighted Network Design in Planar and Minor-closed Families of Graphs
  Chandra Chekuri, Alina Ene, Ali Vakilian.
  ICALP 2012

Talks

• 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)
• Learning Online Algorithms with Distributional Advice
  • Algorithms Under Uncertainty Workshop at FSTTCS’22, IIT Madras (12/6/22)
• Algorithm Design in the Machine Learning Era
  • Research at TTIC (5/13/22)
• Individually Fair Clustering
  • IDEAL Workshop on Clustering, Northwestern (4/23/22)
• Algorithms for Socially Fair Clustering
  • University of Wisconsin—Madison, IFDS (6/10/21)
• Approximation Algorithms for Fair Clustering
  • UCSD, Theory Seminar (5/17/21)
  • UWaterloo, Combinatorics & Optimization Department (5/17/21)
  • MIT, A&C Seminar (5/10/21)
  • TOC4Fairness Seminar (4/28/21)
  • Joint Purdue and UMichigan Theory Seminar (4/23/21)
  • UW Seattle, Theory Seminar (4/20/21)
  • UIUC, Theory Seminar (4/19/21)
  • Google Research (4/15/21)
• Learning-based Algorithms For Massive Data
  • INFORMS Annual Meeting (10/10/20)

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.