3 papers
cs.CC2017
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…
cs.DS2017
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…
cs.DS2017
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…