215 citations · 689 across the 60 of their papers we have counts for
73 papers
Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model
Dani Dorfmann, Dani Dorfman, Simon Döring +5
If we run a heavy-duty computation on prior data, can we avoid repeated computation for similar future inputs? Inspired by this question, we introduce a new computational model for…
Minimum -- Cuts with Fewer Cut Queries
Yonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya
We study the problem of computing a minimum -- cut in an unweighted, undirected graph via \emph{cut queries}. In this model, the input graph is accessed through an oracle tha…
Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions
Martin G. Herold, Danupon Nanongkai, Joachim Spoerhase +2
Geometric data structures have been extensively studied in the regime where the dimension is much smaller than the number of input points. But in many scenarios in Machine Learning…
Shortcuts and Transitive-Closure Spanners Approximation
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay +1
We study polynomial-time approximation algorithms for two closely-related problems, namely computing shortcuts and transitive-closure spanners (TC spanners). For a directed unweigh…
Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao +5
This paper presents parallel, distributed and quantum algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework t…
Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai +1
We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a "unified" al…