61 citations · 66 across the 7 of their papers we have counts for
7 papers
Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems
Mahdi Boroujeni, Sina Dehghani, Soheil Ehsani +2
Despite persistent efforts, there is no known technique for obtaining unconditional super-linear lower bounds for the computational complexity of the problems in P. Vassilevska Wil…
Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi +2
The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another…
Prophet Secretary for Combinatorial Auctions and Matroids
Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim +1
The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items…
Stochastic k-Server: How Should Uber Work?
Sina Dehghani, Soheil Ehsani, MohammadTaghi HajiAghayi +2
In this paper, we study a stochastic variant of the celebrated k-server problem. In the k-server problem, we are required to minimize the total movement of k servers that are servi…
Beating 1-1/e for Ordered Prophets
Melika Abolhasani, Soheil Ehsani, Hosein Esfandiari +3
Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of on the approximation factor…
Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering
Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi +3
We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest(EW-DB-SF) problem and its generalized variant. We o…