12 citations · 59 across the 19 of their papers we have counts for
27 papers
Constant-Factor Local Approximation for Bipartite Densest Subgraph
Michael Kapralov, Jakub Łącki, Silvio Lattanzi +1
Given a vertex in a large bipartite graph , can one quickly find a small densely connected region near ? This is the algorithmic core of many fraud detection, community d…
Dynamic PageRank: Algorithms and Lower Bounds
Rajesh Jayaram, Jakub Łącki, Slobodan Mitrović +2
We consider the PageRank problem in the dynamic setting, where the goal is to explicitly maintain an approximate PageRank vector for a graph under a sequence of…
Fully Dynamic Consistent -Center Clustering
Jakub Łącki, Bernhard Haeupler, Christoph Grunau +2
We study the consistent k-center clustering problem. In this problem, the goal is to maintain a constant factor approximate -center solution during a sequence of point inser…
Constant Approximation for Normalized Modularity and Associations Clustering
Jakub Łącki, Vahab Mirrokni, Christian Sohler
We study the problem of graph clustering under a broad class of objectives in which the quality of a cluster is defined based on the ratio between the number of edges in the cluste…
Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth
Laxman Dhulipala, David Eisenstat, Jakub Łącki +2
Obtaining scalable algorithms for hierarchical agglomerative clustering (HAC) is of significant interest due to the massive size of real-world datasets. At the same time, efficient…
Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds
Sepehr Assadi, Vaggos Chatziafratis, Jakub Łącki +2
The Hierarchical Clustering (HC) problem consists of building a hierarchy of clusters to represent a given dataset. Motivated by the modern large-scale applications, we study the p…
Optimal Decremental Connectivity in Non-Sparse Graphs
Anders Aaman, Adam Karczmarz, Jakub Łącki +3
We present a dynamic algorithm for maintaining the connected and 2-edge-connected components in an undirected graph subject to edge deletions. The algorithm is Monte-Carlo randomiz…
Scalable Community Detection via Parallel Correlation Clustering
Jessica Shi, Laxman Dhulipala, David Eisenstat +2
Graph clustering and community detection are central problems in modern data mining. The increasing need for analyzing billion-scale data calls for faster and more scalable algorit…
Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time
Laxman Dhulipala, David Eisenstat, Jakub Łącki +2
We study the widely used hierarchical agglomerative clustering (HAC) algorithm on edge-weighted graphs. We define an algorithmic framework for hierarchical agglomerative graph clus…
Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari +3
We study fundamental graph problems such as graph connectivity, minimum spanning forest (MSF), and approximate maximum (weight) matching in a distributed setting. In particular, we…
Near-Optimal Decremental Hopsets with Applications
Jakub Łącki, Yasamin Nazari
Given a weighted undirected graph , a hopset of hopbound and stretch is a set of edges such that for any pair of nodes , there is a path in $…
Faster DBSCAN via subsampled similarity queries
Heinrich Jiang, Jennifer Jang, Jakub Łącki
DBSCAN is a popular density-based clustering algorithm. It computes the -neighborhood graph of a dataset and uses the connected components of the high-degree nodes to decide the…
Fully Dynamic Matching: Beating 2-Approximation in Update Time
Soheil Behnezhad, Jakub Łącki, Vahab Mirrokni
In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and de…
Near-Optimal Massively Parallel Graph Connectivity
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari +2
Identifying the connected components of a graph, apart from being a fundamental problem with countless applications, is a key primitive for many other algorithms. In this paper, we…
Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
Adam Karczmarz, Jakub Łącki
We give new partially-dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm f…
Walking Randomly, Massively, and Efficiently
Jakub Łącki, Slobodan Mitrović, Krzysztof Onak +1
We introduce a set of techniques that allow for efficiently generating many independent random walks in the Massive Parallel Computation (MPC) model with space per machine strongly…
Massively Parallel Computation via Remote Memory Access
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari +3
We introduce the Adaptive Massively Parallel Computation (AMPC) model, which is an extension of the Massively Parallel Computation (MPC) model. At a high level, the AMPC model stre…
Connected Components at Scale via Local Contractions
Jakub Łącki, Vahab Mirrokni, Michał Włodarczyk
As a fundamental tool in hierarchical graph clustering, computing connected components has been a central problem in large-scale data mining. While many known algorithms have been…
Decremental SPQR-trees for Planar Graphs
Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz +2
We present a decremental data structure for maintaining the SPQR-tree of a planar graph subject to edge contractions and deletions. The update time, amortized over operation…
Contracting a Planar Graph Efficiently
Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz +3
We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access…
Decremental Single-Source Reachability in Planar Digraphs
Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki +1
In this paper we show a new algorithm for the decremental single-source reachability problem in directed planar graphs. It processes any sequence of edge deletions in $O(n\log^2{n}…
Optimal Dynamic Strings
Paweł Gawrychowski, Adam Karczmarz, Tomasz Kociumaka +2
In this paper we study the fundamental problem of maintaining a dynamic collection of strings under the following operations: concat - concatenates two strings, split - splits a st…
Algorithmic Complexity of Power Law Networks
Paweł Brach, Marek Cygan, Jakub Łącki +1
It was experimentally observed that the majority of real-world networks follow power law degree distribution. The aim of this paper is to study the algorithmic complexity of such "…
Fast and simple connectivity in graph timelines
Adam Karczmarz, Jakub Łącki
In this paper we study the problem of answering connectivity queries about a \emph{graph timeline}. A graph timeline is a sequence of undirected graphs on a common…