AVAli Vakilian

Ali Vakilian

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Ali Vakilian has a total of 6 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Graph-Based Nearest-Neighbor Search without the Spread

    by Jeff Giliberti, Sariel Har-Peled, Jonas Sauer, Ali Vakilian

    $\renewcommand{\Re}{\mathbb{R}}$Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in $\Re^d$, such that one can answer approximate nearest-neighbor queries in logarithmic time in the spread. Unfortunately, the spread might be unbounded in $n$, and an interesting theoretical question is how to remove the dependency on the spread. Here, we show how to construct an external linear-size data structure that, combined with the linear-size graph, allows us to answer ANN queries in logarithmic time in $n$.

  • Open Access

    Sublinear Metric Steiner Forest via Maximal Independent Set

    by Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian

    In this work we consider the Metric Steiner Forest problem in the sublinear time model. Given a set $V$ of $n$ points in a metric space where distances are provided by means of query access to an $n\times n$ distance matrix, along with a set of $k$ terminal pairs $(s_1,t_1), \dots, (s_k,t_k)\in V\times V$, the goal is to find a minimum-weight subset of edges that connects each terminal pair. Although sublinear time algorithms have been studied for estimating the weight of a minimum spanning tree in both general and metric settings, as well as for the metric Steiner Tree problem, no sublinear time algorithm was known for the metric Steiner Forest problem. Here, we give an $O(\log k)$-approximation algorithm for the problem that runs in time $\widetilde{O}(n^{3/2})$. Along the way, we provide the first sublinear-time algorithm for estimating the size of a Maximal Independent Set (MIS). Our algorithm runs in time $\widetilde{O}(n^{3/2}/\varepsilon^2)$ under the adjacency matrix oracle model and obtains a purely multiplicative $(1+\varepsilon)$-approximation. Previously, sublinear-time algorithms for MIS were only known for bounded-degree graphs.