4 papers
Fractal dimension and lower bounds for geometric problems
Anastasios Sidiropoulos, Kritika Singhal, Vijay Sridhar
We study the complexity of geometric problems on spaces of low fractal dimension. It was recently shown by [Sidiropoulos & Sridhar, SoCG 2017] that several problems admit improved…
On constant multi-commodity flow-cut gaps for directed minor-free graphs
Ario Salmasi, Anastasios Sidiropoulos, Vijay Sridhar
The multi-commodity flow-cut gap is a fundamental parameter that affects the performance of several divide \& conquer algorithms, and has been extensively studied for various class…
Algorithmic interpretations of fractal dimension
Anastasios Sidiropoulos, Vijay Sridhar
We study algorithmic problems on subsets of Euclidean space of low fractal dimension. These spaces are the subject of intensive study in various branches of mathematics, including…
Quasimetric embeddings and their applications
Facundo Mémoli, Anastasios Sidiropoulos, Vijay Sridhar
We study generalizations of classical metric embedding results to the case of quasimetric spaces; that is, spaces that do not necessarily satisfy symmetry. Quasimetric spaces arise…