Arrow Research search

Author name cluster

Gramoz Goranci

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers
2 author rows

Possible papers

16

NeurIPS Conference 2025 Conference Paper

Fully Dynamic Algorithms for Chamfer Distance

  • Gramoz Goranci
  • Shaofeng Jiang
  • Peter Kiss
  • Eva Szilagyi
  • Qiaoyuan Yang

We study the problem of computing Chamfer distance in the fully dynamic setting, where two sets of points $A, B \subset \mathbb{R}^{d}$, each of size up to $n$, dynamically evolve through point insertions or deletions and the goal is to efficiently maintain an approximation to $dist_{\mathrm{CH}}(A, B) = \sum_{a \in A} \min_{b \in B} dist(a, b)$, where $dist$ is a distance measure. Chamfer distance is a widely used dissimilarity metric for point clouds, with many practical applications that require repeated evaluation on dynamically changing datasets, e. g. , when used as a loss function in machine learning. In this paper, we present the first dynamic algorithm for maintaining an approximation of the Chamfer distance under the $\ell_p$ norm for $p \in$ {$1, 2$}. Our algorithm reduces to approximate nearest neighbor (ANN) search with little overhead. Plugging in standard ANN bounds, we obtain $(1+\epsilon)$-approximation in $\tilde{O}(\epsilon^{-d})$ update time and $O(1/\epsilon)$-approximation in $\tilde{O}(d n^{\epsilon^2} \epsilon^{-4})$ update time. We evaluate our method on real-world datasets and demonstrate that it performs competitively against natural baselines.

PDF Details

ICML Conference 2025 Conference Paper

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time

  • Gramoz Goranci
  • Peter Kiss
  • Neel Patel
  • Martin P. Seybold
  • Eva Szilagyi
  • Da Wei Zheng

We consider the Euclidean bi-chromatic matching problem in the dynamic setting, where the goal is to efficiently process point insertions and deletions while maintaining a high-quality solution. Computing the minimum cost bi-chromatic matching is one of the core problems in geometric optimization that has found many applications, most notably in estimating Wasserstein distance between two distributions. In this work, we present the first fully dynamic algorithm for Euclidean bi-chromatic matching with sublinear update time. For any fixed $\varepsilon > 0$, our algorithm achieves $O(1/\varepsilon)$-approximation and handles updates in $O(n^{\varepsilon})$ time. Our experiments show that our algorithm enables effective monitoring of the distributional drift in the Wasserstein distance on real and synthetic data sets, while outperforming the runtime of baseline approximations by orders of magnitudes.

Details

ICML Conference 2024 Conference Paper

Dynamic Facility Location in High Dimensional Euclidean Spaces

  • Sayan Bhattacharya
  • Gramoz Goranci
  • Shaofeng H. -C. Jiang
  • Yi Qian
  • Yubo Zhang

We study the facility location problem in the dynamic setting, where the goal is to efficiently process an intermixed sequence of point insertions and deletions while maintaining a high quality and stable solution. Although the problem has been studied in the context of general metrics and low-dimensional spaces, much remains unknown concerning dynamic facility location in high dimensional spaces. In this work, we present the first fully dynamic algorithm for facility location in high-dimensional spaces $\mathbb{R}^{d}$. For any $c \geq 1$, our algorithm achieves $O(c)$-approximation, supports point updates in $\tilde{O}(\mathrm{poly}(d)n^{1/c + o(1)})$ amortized time and incurs $O(1)$ amortized recourse. More generally, our result shows that despite the linear-time lower bound on the update time for general metrics, it is possible to achieve sub-linear update times for metric spaces that admit dynamic nearest neighbour oracles. Experiments on real datasets confirm that our algorithm achieves high-quality solutions with low running time, and incurs minimal recourse.

Details

FOCS Conference 2024 Conference Paper

Near-Optimal (1+ε)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs

  • Arnold Filtser
  • Gramoz Goranci
  • Neel Patel
  • Maximilian Probst Gutenberg

We study the fully-dynamic all-pair shortest paths (APSP) problem on planar graphs: given an $n-\mathbf{vertex}$ planar graph $G=(V, E)$ undergoing edge insertions and deletions, the goal is to efficiently process these updates and support distance and shortest path queries. We give a $(1+\epsilon)-\mathbf{approximate}$ dynamic algorithm that supports edge updates and distance queries in $n^{o(1)}$ time, for any $1/\mathbf{poly}(\log n) < \epsilon < 1$. Our result is a significant improvement over the best previously known bound of $\tilde{O}(\sqrt{n})$ on update and query time due to [Abraham, Chechik, and Gavoille, STOC ’12], and bypasses a $\Omega(\sqrt{n})$ conditional lower-bound on update and query time for exact fully dynamic planar APSP [Abboud and Dahlgaard, FOCS ’16]. The main technical contribution behind our result is to dynamize the planar emulator construction due to [Chang, Krauthgamer, Tan, STOC ’22].

Details

FOCS Conference 2021 Conference Paper

Minor Sparsifiers and the Distributed Laplacian Paradigm

  • Sebastian Forster
  • Gramoz Goranci
  • Yang P. Liu
  • Richard Peng
  • Xiaorui Sun
  • Mingquan Ye

We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrices to high accuracy. Our Laplacian solver has a round complexity of $O(n^{o(1)}(\sqrt{n}+D))$, and thus almost matches the lower bound of $\widetilde{\Omega}(\sqrt{n}+D)$, where $n$ is the number of nodes in the network and $D$ is its diameter. We show that our distributed solver yields new sublinear round algorithms for several cornerstone problems in combinatorial optimization. This is achieved by leveraging the powerful algorithmic framework of Interior Point Methods (IPMs) and the Laplacian paradigm in the context of distributed graph algorithms, which entails numerically solving optimization problems on graphs via a series of Laplacian systems. Problems that benefit from our distributed algorithmic paradigm include exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on sparse directed graphs. For the maxflow problem, this is the first exact distributed algorithm that applies to directed graphs, while the previous work by [Ghaffari et al. SICOMP'18] considered the approximate setting and works only for undirected graphs. For the mincost flow and the negative weight shortest path problems, our results constitute the first exact distributed algorithms running in a sublinear number of rounds. Given that the hybrid between IPMs and the Laplacian paradigm has proven useful for tackling numerous optimization problems in the centralized setting, we believe that our distributed solver will find future applications. At the heart of our distributed Laplacian solver is the notion of spectral subspace sparsifiers of [Li, Schild FOCS'18]. We present a nontrivial distributed implementation of their construction by (i) giving a parallel variant of their algorithm that avoids the sampling of random spanning trees and uses approximate leverage scores instead, and (ii) showing that the algorithm still produces a high-quality subspace spectral sparsifier by carefully setting up and analyzing matrix martingales. Combining this vertex reduction recursively with both tree and elimination-based preconditioners leads to our algorithm for solving Laplacian systems. The construction of the elimination-based preconditioners is based on computing short random walks, and we introduce a new technique for reducing the congestion incurred by the simulation of these walks on weighted graphs.

Details

FOCS Conference 2020 Conference Paper

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers

  • Li Chen 0028
  • Gramoz Goranci
  • Monika Henzinger
  • Richard Peng
  • Thatchaphol Saranurak

We present a general framework of designing efficient dynamic approximate algorithms for optimization problems on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1)A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in $\tilde{O}(n^{2/3})$ 1 1 The $\tilde{O}(\cdot)$ notation is used in this paper to hide poly-logarithmic factors. amortized time against an oblivious adversary, and $\tilde{O}(m^{3/4})$ time against an adaptive adversary. (2)An incremental data structure that maintains $O(1)$ - approximate shortest path in $n^{o(1)}$ time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in $\tilde{O}(n^{2/3 +o(1)})$ amortized time per operation. (3)A fully-dynamic algorithm that approximates all-pair effective resistance up to an ( $1+\epsilon$ ) factor in $\tilde{O}(n^{2/3+o(1)}\epsilon^{-O(1)})$ amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as $j$ -trees) and approximately captures the cut-flow and metric structure of the graph. The $O(1)$ -approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM '05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC '19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy. See https: //arxiv. org/pdf/2005. 02368. pdf for the full version of this paper.

Details

ICML Conference 2020 Conference Paper

Faster Graph Embeddings via Coarsening

  • Matthew Fahrbach
  • Gramoz Goranci
  • Richard Peng
  • Sushant Sachdeva
  • Chi Wang 0001

Graph embeddings are a ubiquitous tool for machine learning tasks, such as node classification and link prediction, on graph-structured data. However, computing the embeddings for large-scale graphs is prohibitively inefficient even if we are interested only in a small subset of relevant vertices. To address this, we present an efficient graph coarsening approach, based on Schur complements, for computing the embedding of the relevant vertices. We prove that these embeddings are preserved exactly by the Schur complement graph that is obtained via Gaussian elimination on the non-relevant vertices. As computing Schur complements is expensive, we give a nearly-linear time algorithm that generates a coarsened graph on the relevant vertices that provably matches the Schur complement in expectation in each iteration. Our experiments involving prediction tasks on graphs demonstrate that computing embeddings on the coarsened graph, rather than the entire graph, leads to significant time savings without sacrificing accuracy.

Details