Arrow Research search

Author name cluster

Peter Kiss

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.

9 papers
2 author rows

Possible papers

9

STOC Conference 2025 Conference Paper

Deterministic Dynamic Maximal Matching in Sublinear Update Time

  • Aaron Bernstein
  • Sayan Bhattacharya
  • Peter Kiss
  • Thatchaphol Saranurak

We give a fully dynamic deterministic algorithm for maintaining a maximal matching of an n -vertex graph in Õ( n 8/9 ) amortized update time. This breaks the long-standing Ω( n )-update-time barrier on dense graphs, achievable by trivially scanning all incident vertices of the updated edge, and affirmatively answers a major open question repeatedly asked in the literature Baswana, Gupta and Sen [FOCS 2011], Bhattacharya,Chakrabarty, Henzinger and Nanongkai [SODA 2018], Solomon [Dagstuhl]. We also present a faster randomized algorithm against an adaptive adversary with Õ( n 3/4 ) amortized update time. Our approach employs the edge degree constrained subgraph (EDCS), a central object for optimizing approximation ratio, in a completely novel way; we instead use it for maintaining a matching that matches all high degree vertices in sublinear update time so that it remains to handle low degree vertices rather straightforwardly. To optimize this approach, we employ tools never used in the dynamic matching literature prior to our work, including sublinear-time algorithms for matching high degree vertices, random walks on directed expanders, and the monotone Even-Shiloach tree for dynamic shortest paths.

Details

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

FOCS Conference 2023 Conference Paper

Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time

  • Sayan Bhattacharya
  • Peter Kiss
  • Thatchaphol Saranurak

We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate size of maximum matching of the graph with n vertices and m edges using $m^{0. 5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial improvement over the long-standing $O(n)$ update time, which can be trivially obtained by periodic recomputation. Thus, we resolve the value version of a major open question of the dynamic graph algorithms literature (see, e. g. , [Gupta and Peng FOCS’13], [Bernstein and Stein SODA’16], [Behnezhad and Khanna SODA’22]). Our key technical component is the first sublinear algorithm for $(1, \epsilon n)$-approximate maximum matching with sublinear running time on dense graphs. All previous algorithms suffered a multiplicative approximation factor of at least 1. 499 or assumed that the graph has a very small maximum degree.

Details

SODA Conference 2023 Conference Paper

Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates

  • Sayan Bhattacharya
  • Peter Kiss
  • Thatchaphol Saranurak

In the dynamic linear program (LP) problem, we are given an LP undergoing updates and we need to maintain an approximately optimal solution. Recently, significant attention (e. g. [Gupta et al. STOC'17; Arar et al. ICALP'18, Wajc STOC'20]) has been devoted to the study of special cases of dynamic packing and covering LPs, such as the dynamic fractional matching and set cover problems. But until now, there is no non-trivial dynamic algorithm for general packing and covering LPs. In this paper, we settle the complexity of dynamic packing and covering LPs, up to a polylogarithmic factor in update time. More precisely, in the partially dynamic setting (where updates can either only relax or only restrict the feasible region), we give near-optimal deterministic ε-approximation algorithms with polylogarithmic amortized update time. Then, we show that both partially dynamic updates and amortized update time are necessary; without any of these conditions, the trivial algorithm that recomputes the solution from scratch after every update is essentially the best possible, assuming SETH. To obtain our results, we initiate a systematic study of the multiplicative weights update (MWU) method in the dynamic setting. As by-products of our techniques, we also obtain the first online (1 + ε)-competitive algorithms for both covering and packing LPs with polylogarithmic recourse, and the first streaming algorithms for covering and packing LPs with linear space and polylogarithmic passes.

Details

SODA Conference 2023 Conference Paper

Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time

  • Sayan Bhattacharya
  • Peter Kiss
  • Thatchaphol Saranurak
  • David Wajc

We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than 2. Specifically, we obtain a approximation in bipartite graphs and a 1. 973 + ε approximation in general graphs. We thus answer in the affirmative the value version of the major open question repeatedly asked in the dynamic graph algorithms literature. Our randomized algorithms' approximation and worst-case update time bounds both hold w. h. p. against adaptive adversaries. Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS'21) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier.

Details