Author name cluster

Shreyas Pai

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.

3 papers

2 author rows

STOC Conference 2025 Conference Paper

Online Locality Meets Distributed Quantum Computing

Amirreza Akbari
Xavier Coiteux-Roy
Francesco d'Amore 0001
François Le Gall
Henrik Lievonen
Darya Melnyk
Augusto Modanese
Shreyas Pai

We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-signaling distributions [e.g. STOC 2024], B. finitely-dependent processes [e.g. Forum Math. Pi 2016], and C. locality in online graph algorithms and dynamic graph algorithms [e.g. ICALP 2023]. We prove new results on the capabilities and limitations of all of these models of computing, for locally checkable labeling problems (LCLs). We show that all these settings can be sandwiched between the classical LOCAL model and what we call the randomized online-LOCAL model. Our work implies limitations on the quantum advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds. Our main technical results are these: (1) All LCL problems solvable with locality O (log ⋆ n ) in the classical deterministic LOCAL model admit a finitely-dependent distribution with locality O (1). This answers an open question by Holroyd [2024], and also presents a new barrier for proving bounds on distributed quantum advantage using causality-based arguments. (2) In rooted trees, if we can solve an LCL problem with locality o (logloglog n ) in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality O (log ⋆ n ) in the classical deterministic LOCAL model. One of many implications is that in rooted trees, O (log ⋆ n ) locality in quantum-LOCAL is not stronger than O (log ⋆ n ) locality in classical LOCAL.

Details

SODA Conference 2024 Conference Paper

A (3 + ɛ)-Approximate Correlation Clustering Algorithm in Dynamic Streams

Mélanie Cambus
Fabian Kuhn
Etna Lindy
Shreyas Pai
Jara Uitto

Grouping together similar elements in datasets is a common task in data mining and machine learning. In this paper, we study streaming and parallel algorithms for correlation clustering, where each pair of elements is labeled either similar or dissimilar. The task is to partition the elements and the objective is to minimize disagreements, that is, the number of dissimilar elements grouped together and similar elements that get separated. Our main contribution is a semi-streaming algorithm that achieves a (3 + ɛ)-approximation to the minimum number of disagreements using a single pass over the stream. In addition, the algorithm also works for dynamic streams. Our approach builds on the analysis of the PIVOT algorithm by Ailon, Charikar, and Newman [JACM’08] that obtains a 3-approximation in the centralized setting. Our design allows us to sparsify the input graph by ignoring a large portion of the nodes and edges without a large extra cost as compared to the analysis of PIVOT. This sparsification makes our technique applicable in several models of massive graph processing, such as semi-streaming and Massively Parallel Computing (MPC), where sparse graphs can typically be handled much more efficiently. Our work improves on the approximation ratio of the recent single-pass 5-approximation algorithm and on the number of passes of the recent O (1/ɛ)-pass (3 + ɛ)-approximation algorithm [Behnezhad, Charikar, Ma, Tan FOCS’22, SODA’23]. Our algorithm is also more robust and can be applied in dynamic streams. Furthermore, it is the first single pass (3 + ɛ)-approximation algorithm that uses polynomial post-processing time.

Details

TCS Journal 2022 Journal Article

Near-optimal clustering in the k-machine model

Sayan Bandyapadhyay
Tanmay Inamdar
Shreyas Pai
Sriram V. Pemmaraju

The clustering problem, in its many variants, has numerous applications in operations research and computer science (e. g. , in applications in bioinformatics, image processing, social network analysis, etc.). As sizes of data sets have grown rapidly, researchers have focused on designing algorithms for clustering problems in models of computation suited for large-scale computation such as MapReduce, Pregel, and streaming models. The k-machine model (Klauck et al. , (SODA 2015) [8]) is a simple, message-passing model for large-scale distributed graph processing. This paper considers three of the most prominent examples of clustering problems: the uncapacitated facility location problem, the p-median problem, and the p-center problem and presents O ( 1 ) -factor approximation algorithms for these problems running in O ˜ ( n / k ) rounds in the k-machine model. These algorithms are optimal up to polylogarithmic factors because this paper also shows Ω ˜ ( n / k ) lower bounds for obtaining polynomial-factor approximation algorithms for these problems. These are the first results for clustering problems in the k-machine model. We assume that the metric provided as input for these clustering problems is only implicitly provided, as an edge-weighted graph and in a nutshell, our main technical contribution is to show that constant-factor approximation algorithms for all three clustering problems can be obtained by learning only a small portion of the input metric.

Details DOI