Ali Vakilian
I am a
Research Assistant Professor at
Toyota Technological Institute—Chicago (TTIC) .
Education
Ph.D., EECS Department, MIT
Advisors: Erik Demaine and Piotr Indyk
M.S., CS Department, University of Illinois at Urbana-Champaign (UIUC)
Advisor: Chandra Chekuri
B.S., CE Department, Sharif University
Research Interests
Learning-Based/Data Driven Algorithms
Algorithmic Fairness
Design and Analysis of Algorithms for Massive Data
Approximation Algorithms, Combinatorial Optimization, and Graph Algorithms
Teaching
Academic Service
CV [Last update: May 2023]
Email: vakilian[at]ttic[dot]edu
Publications
Massive Data
Graph Algorithms
Machine Learning
Preprints
Conference Papers
Manuscripts
Theses
New Directions
in Streaming Algorithms
[abstract]
Large volumes of available data have led to the emergence of new computational models for
data analysis. One such model is captured by the notion of streaming algorithms: given a
sequence of N items, the goal is to compute the value of a given function of the input items by
a small number of passes and using a sublinear amount of space in N . Streaming algorithms
have applications in many areas such as networking and large scale machine learning. Despite
a huge amount of work on this area over the last two decades, there are multiple aspects
of streaming algorithms that remained poorly understood, such as (a) streaming algorithms
for combinatorial optimization problems and (b) incorporating modern machine learning
techniques in the design of streaming algorithms.
In the first part of this thesis, we will describe (essentially) optimal streaming algorithms
for set cover and maximum coverage, two classic problems in combinatorial optimization.
Next, in the second part, we will show how to augment classic streaming algorithms of the
frequency estimation and low-rank approximation problems with machine learning oracles
in order to improve their space-accuracy tradeoffs. The new algorithms combine the benefits
of machine learning with the formal guarantees available through algorithm design theory.
[ DSpace@MIT ]
Ph.D. thesis , Department of EECS, MIT, 2019.
Node-Weighted
Prize-Collecting Survivable Network Design Problems
[abstract]
We consider node-weighted network design problems, in particular the survivable network
design problem (SNDP) and its prize-collecting version (PC-SNDP). The input consists of a
node-weighted undirected graph G = (V;E) and integral connectivity requirements
r(st) for each pair of nodes st . The goal is to find a minimum node-weighted
subgraph H of G such that, for each pair st , H contains r(st)
disjoint paths between s and t . PC-SNDP is a generalization in which the input
also includes a penalty π(st) for each pair, and the goal is to find a subgraph H
to minimize the sum of the weight of H and the sum of the penalties for all pairs
whose connectivity requirements are not fully satisfied by H. We consider three types of
connectivity requirements, edge-connectivity (EC), element-connectivity (ELC) and
vertex-connectivity (VC). Let k = maxst r(st) be the maximum requirement.
There has been no non-trivial approximation for node-weighted PC-SNDP for k > 1 even in
edge-connectivity setup. We describe multiroute-flow based relaxations for PC-EC-SNDP and
PC-ELC-SNDP and obtain approximation algorithms for PC-SNDP and PC-ELC-SNDP through them.
The approximation ratios we obtain for PC-EC-SNDP are similar to those that were previously
known for EC-SNDP via combinatorial algorithms. Specifically, for PC-EC-SNDP (and PC-ELC-SNDP)
we obtain an O(k log n) -approximation in general graphs and an O(k) -approximation
in graphs that exclude a fixed minor. Moreover, based on the approximation algorithm of ELC-SNDP
and the reduction method of [Chuzhoy and Khanna, Theory of Computing 2012] we obtain
O(k4 log2 n) -approximation for PC-VC-SNDP which improves to
O(k4 log n) on instances from a minor-closed families of graphs.
[ IDEALS@UIUC ]
M.S. thesis , Department of Computer Science, UIUC, 2013.
Publication Profiles
Talks
Algorithm Design in the Machine Learning Era
Research at TTIC; May 13, 2022
Individually Fair Clustering [ video ]
IDEAL Workshop on Clustering; April 23, 2022
Algorithms for Socially Fair Clustering
University of Wisconsin—Madison, IFDS; June 10, 2021
Approximation Algorithms for Fair Clustering
Google Research; April 15, 2021.
UIUC, Department of Computer Science; April 19, 2021.
University of Washington; April 20, 2021.
Joint Purdue University and University of Michigan Theory Seminar; April 23 2021.
TOC4Fairness Seminar; April 28, 2021.
MIT A&C Seminar; May 10, 2021.
UC San Diego, Department of Computer Science & Engineering; May 17, 2021.
UWaterloo, Combinatoics & Optimization Department; May 17, 2021.
Learning-based Algorithms For Massive Data
INFORMS Annual Meeting; November 10, 2020.