Zobrazeno 1 - 10
of 806
pro vyhledávání: '"Lacki, P."'
Autor:
De Man, Quinten, Dhulipala, Laxman, Karczmarz, Adam, Łącki, Jakub, Shun, Julian, Wang, Zhongqi
We study the problem of dynamically maintaining the connected components of an undirected graph subject to edge insertions and deletions. We give the first parallel algorithm for the problem which is work-efficient, supports batches of updates, runs
Externí odkaz:
http://arxiv.org/abs/2411.11781
Autor:
Yu, Shangdi, Shi, Jessica, Meindl, Jamison, Eisenstat, David, Ju, Xiaoen, Tavakkol, Sasan, Dhulipala, Laxman, Łącki, Jakub, Mirrokni, Vahab, Shun, Julian
We introduce the ParClusterers Benchmark Suite (PCBS) -- a collection of highly scalable parallel graph clustering algorithms and benchmarking tools that streamline comparing different graph clustering algorithms and implementations. The benchmark in
Externí odkaz:
http://arxiv.org/abs/2411.10290
The SetCover problem has been extensively studied in many different models of computation, including parallel and distributed settings. From an approximation point of view, there are two standard guarantees: an $O(\log \Delta)$-approximation (where $
Externí odkaz:
http://arxiv.org/abs/2408.13362
Autor:
Azarmehr, Amir, Behnezhad, Soheil, Jayaram, Rajesh, Łącki, Jakub, Mirrokni, Vahab, Zhong, Peilin
We study the minimum spanning tree (MST) problem in the massively parallel computation (MPC) model. Our focus is particularly on the *strictly sublinear* regime of MPC where the space per machine is $O(n^\delta)$. Here $n$ is the number of vertices a
Externí odkaz:
http://arxiv.org/abs/2408.06455
Autor:
Korbmacher, Henning, Domínguez-Castro, Gustavo A., Łącki, Mateusz, Zakrzewski, Jakub, Santos, Luis
Ultracold dipolar hard-core bosons in optical ladders provide exciting possibilities for the quantum simulation of anisotropic XXZ spin ladders. We show that introducing a tilt along the rungs results in a rich phase diagram at unit filling. In parti
Externí odkaz:
http://arxiv.org/abs/2407.15710
Autor:
Bateni, MohammadHossein, Dhulipala, Laxman, Fletcher, Willem, Gowda, Kishen N, Hershkowitz, D Ellis, Jayaram, Rajesh, Łącki, Jakub
We give an efficient algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a $c$-approximate clustering in roughly $n^{1+O(1/c^2)}$ time. We obtain our result by combining a new Centroid-Linkage HAC algorithm with
Externí odkaz:
http://arxiv.org/abs/2406.05066
Autor:
Wheatman, Brian, Dong, Xiaojun, Shen, Zheqi, Dhulipala, Laxman, Łącki, Jakub, Pandey, Prashant, Xu, Helen
A fundamental building block in any graph algorithm is a graph container - a data structure used to represent the graph. Ideally, a graph container enables efficient access to the underlying graph, has low space usage, and supports updating the graph
Externí odkaz:
http://arxiv.org/abs/2405.11671
Autor:
Lacki, Brian C.
Publikováno v:
ApJ 966, 183 (2024)
The search for extraterrestrial intelligence includes efforts to constrain populations of artificial broadcasts in other galaxies. Previous efforts use individualist methods, searching for single broadcasts with high signal-to-noise ratio. These woul
Externí odkaz:
http://arxiv.org/abs/2405.04651
Autor:
Lacki, Brian C.
Publikováno v:
ApJ 966, 182 (2024)
Artificial broadcasts from extraterrestrial intelligences (ETIs) are a hypothetical class of celestial phenomena. Unlike known astrophysical objects, the societies that generate them may be able to replicate on galactic scales through interstellar tr
Externí odkaz:
http://arxiv.org/abs/2405.04646
We consider the PageRank problem in the dynamic setting, where the goal is to explicitly maintain an approximate PageRank vector $\pi \in \mathbb{R}^n$ for a graph under a sequence of edge insertions and deletions. Our main result is a complete chara
Externí odkaz:
http://arxiv.org/abs/2404.16267