2 citations · 4 across the 8 of their papers we have counts for
10 papers
Faster Sublinear Maximal Independent Set Size
Peter Kiss, Arash Kooroshnezhad
We give a sublinear-time algorithm for estimating the size of a maximal independent set in a graph using adjacency-query access with expected running time , i…
Online Preemptive Matching Revisited
Peter Kiss, Mohammad Sharifi
We study the online preemptive matching problem, in which the edges of a graph arrive sequentially and the algorithm must maintain a matching by accepting or rejecting arriving edg…
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer +2
We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, bas…
Deterministic Dynamic Maximal Matching in Sublinear Update Time
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss +1
We give a fully dynamic deterministic algorithm for maintaining a maximal matching of an -vertex graph in amortized update time. This breaks the long-standi…
Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
Sepehr Assadi, Sanjeev Khanna, Peter Kiss
In a very recent breakthrough, Behnezhad and Ghafari [FOCS'24] developed a novel fully dynamic randomized algorithm for maintaining a -approximation of maximum matching with…
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
Sayan Bhattacharya, Peter Kiss, Aaron Sidford +1
We study dynamic -approximate rounding of fractional matchings -- a key ingredient in numerous breakthroughs in the dynamic graph algorithms literature. Our first contributi…
Incremental -approximate dynamic matching in update time
Joakim Blikstad, Peter Kiss
In the dynamic approximate maximum bipartite matching problem we are given bipartite graph undergoing updates and our goal is to maintain a matching of which is large compa…
Dynamic -Approximate Matching Size in Truly Sublinear Update Time
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
We show a fully dynamic algorithm for maintaining -approximate \emph{size} of maximum matching of the graph with vertices and edges using update tim…
Client Error Clustering Approaches in Content Delivery Networks (CDN)
Ermiyas Birihanu, Jiyan Mahmud, Péter Kiss +6
Content delivery networks (CDNs) are the backbone of the Internet and are key in delivering high quality video on demand (VoD), web content and file services to billions of users.…
Matrix Factorization for Cache Optimization in Content Delivery Networks (CDN)
Adolf Kamuzora, Wadie Skaf, Ermiyas Birihanu +6
Content delivery networks (CDNs) are key components of high throughput, low latency services on the internet. CDN cache servers have limited storage and bandwidth and implement sta…