Ali Vakilian
I am a final-year PhD student in the Theory of Computation group at CSAIL, MIT. I am fortunate to have Erik Demaine and Piotr Indyk as my advisors.
Prior to my PhD studies at MIT, I did my master's studies at UIUC where I was lucky to be advised by Chandra Chekuri. I received my bachelor's degree in Computer Engineering from Sharif University of Technology.
My Research Interests lie in theoretical computer science and its applications. More specifically,
  • Design and Analysis of Algorithms for Massive Data
  • Augmenting Algorithms with Machine Learned Advice
  • Approximation Algorithms, Combinatorial Optimization, and Graph Algorithms

CV [Last update: December 2018]

Email: vakilian[at]mit[dot]edu
Publications (click on [+/-] to see a short summary of each result)
Massive Data Graph Algorithms Machine Learning
  • Tight Tradeoffs for Maximum k-Coverage Problem in the General Streaming Model MD
    Piotr Indyk, Ali Vakilian. December 2018.
    We provided a tight trade-off between the space complexity and approximation factor of any single-pass streaming algorithm that estimates the maximum coverage size in the general edge-arrival streaming model (i.e. element-set pairs). This work is among a very few known results on design of streaming algorithms for combinatorial optimization tasks that exploit vector sketching techniques (e.g., lp-norm estimation and heavy hitters)
  • Approximation Algorithms for Nearly H-Minor-Free Graphs GA
    Erik Demaine, Quanquan Liu, Ali Vakilian. November 2018 .
    In this work, we generalized existing PTASes for bidimensional parameters on H-minor free graphs to graphs that are somewhat near H-minor free.
  • Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class GA
    Erik Demaine, Timothy Goodrich, Kyle Kloster, Brian Lavallee, Quanquan Liu, Blair Sullivan, Ali Vakilian, Andrew van der Poel. November 2018.
    We developed a generic framework to “round” an input graph into a family of graphs with “certain structures” using a small number of “edits”, then solve the problem on the edited structured graph, and finally “lift” the solution back to get a near optimal solution in the original graph. This rounding framework in particular implies algorithms with improved approximation factors for many classical NP-hard problems such as vertex cover, feedback vertex set, independent set, and many variants of dominating set on graphs close to bounded degenerate, bounded treewidth.
  • Learning-Based Frequency Estimation Algorithms MD ML
    Chen-Yu Hsu, Piotr Indyk, Dina Katabi, Ali Vakilian. ICLR 2019.
    We augmented the existing algorithms for frequency estimation with a machine learned oracle for the task of finding heavy hitters. Besides the empirical improvement over the existing methods for frequency estimation (such as Count-Min and Count-Sketch), our approach provably provides better guarantees if the input distribution has certain structure. Moreover, in the worst case scenario, our algorithms match the performance of the best known algorithms for frequency estimation.
  • Local Computation Algorithms for Spanners
    Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee. ITCS 2019.
    We designed the first sub-linear time LCAs for several variants of spanners with constant stretch in general graphs. Generally speaking, given an edge (u,v), our algorithm decides whether the edge is in the spanner in o(|V|). Furthermore, the partial answers altogether constitute a single valid output.
  • Set Cover in Sub-linear Time
    Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee. SODA 2018.
    We provided tight sub-linear algorithms for Set Cover in query access model. Our lower bound results follow by designing two distributions of Set Cover instances that are hard to distinguish.
  • Fractional Set Cover in the Streaming Model
    Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, Anak Yodpinyanee. APPROX 2017.
    We presented a constant-pass algorithm for solving fractional set cover near-optimally in sub-linear space. This was the first instance of covering LPs with a constant pass algorithm in the streaming model. Our algorithm finds a (1+ε)-approximate solution employing the multiplicative weight update method.
  • Cost-Effective Conceptual Design Over Taxonomies
    Ali Vakilian, Yodsawalai Chodpathumwan, Arash Termehchy, Amir Nayyeri. WebDB 2017.
    Also in VLDB Journal 2018.
  • Towards Tight Bounds for the Streaming Set Cover Problem
    Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi, Ali Vakilian. PODS 2016.
    We developed improved constant-pass streaming algorithms for Set Cover. The algorithms turned out to be “the optimal” algorithm for Set Cover (and some other related problems) in several massive data models in subsequent work by us and other researchers.
  • On Streaming and Communication Complexity of The Set Cover Problem MD
    Erik Demaine, Piotr Indyk, Sepideh Mahabadi, Ali Vakilian. DISC 2014.
    We introduced the “low-approximate” streaming Set Cover where the goal is to obtain near log(n)-approximate solution of Set Cover and presented the first constant-pass algorithm with sub-linear space.
  • Which Concepts are Worth Extracting?
    Arash Termehchy, Ali Vakilian, Yodsawalai Chodpathumwan, Marianne Winslett. SIGMOD 2014.
    Also in Transactions on Database Systems (TODS) 2015.
  • Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements
    Alina Ene, Ali Vakilian. STOC 2014.
    we presented the first (O(1),O(1))-bicriteria approximations for several variants of degree-bounded Survivable Network Design problems (SNDP) (e.g. VC-SNDP, k-connected subgraph) addressing several important open questions in the area by Fukunaga-Nutov-Ravi and Cheriyan-Vegh.
  • Connected Domatic Packing in Node-capacitated Graphs GA
    Alina Ene, Nitish Korula, Ali Vakilian. July 2013.
    Besides our results on fractionally packing connected dominating sets, we designed the first constant factor approximation algorithm for minimum connected dominating set on H-minor-free graphs.
  • Prize-collecting Survivable Network Design in Node-weighted Graphs GA
    Chandra Chekuri, Alina Ene, Ali Vakilian. APPROX 2012 .
    We developed the first non-trivial approximation algorithm for the node-weighted prize-collecting Survivable Network Design problem (SNDP): O(k log n)-approximation where k is the maximum connectivity requirement between any pair of vertices. This improves to O(k) on minor-closed families of graphs. One of our contributions was to define a novel LP relaxation for node-weighted SNDP based on multi-route flows.
  • Node-weighted Network Design in Planar and Minor-closed Families of Graphs GA
    Chandra Chekuri, Alina Ene, Ali Vakilian. ICALP 2012.
    We considered the node-weighted Survivable Network Design problem (SNDP) on minor-closed families of graphs. Our algorithm achieves an O(k)-approximation where k is the maximum connectivity requirement of any pair of vertices, which improves upon the O(k log n)-approximation of the node-weighted SNDP on general graphs.
Thesis
Publication Profiles
Honors and Awards
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.