1k citations · 1.7k across the 27 of their papers we have counts for
14 papers · 1 filter
Constant Arboricity Spectral Sparsifiers
Timothy Chu, Michael B. Cohen, Jakub W. Pachocki +1
We show that every graph is spectrally similar to the union of a constant number of forests. Moreover, we show that Spielman-Srivastava sparsifiers are the union of O(logn) forests…
A Framework for Analyzing Resparsification Algorithms
Rasmus Kyng, Jakub Pachocki, Richard Peng +1
A spectral sparsifier of a graph is a sparser graph that approximately preserves the quadratic form of , i.e. for all vectors , , where $…
Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners
Jakub Pachocki, Liam Roditty, Aaron Sidford +2
The girth of a graph, i.e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and g…
Geometric Median in Nearly Linear Time
Michael B. Cohen, Yin Tat Lee, Gary Miller +2
In this paper we provide faster algorithms for solving the geometric median problem: given points in compute a point that minimizes the sum of Euclidean distan…
Scalable motif-aware graph clustering
Charalampos Tsourakakis, Jakub Pachocki, Michael Mitzenmacher
We develop new methods based on graph motifs for graph clustering, allowing more efficient detection of communities within networks. We focus on triangles within graphs, but our te…
Analysis of Resparsification
Jakub Pachocki
We show that schemes for sparsifying matrices based on iteratively resampling rows yield guarantees matching classic 'offline' sparsifiers (see e.g. Spielman and Srivastava [STOC 2…
Online Row Sampling
Michael B. Cohen, Cameron Musco, Jakub Pachocki
Finding a small spectral approximation for a tall matrix is a fundamental numerical primitive. For a number of reasons, one often seeks an approximation whose rows…
Routing under Balance
Alina Ene, Gary Miller, Jakub Pachocki +1
We introduce the notion of balance for directed graphs: a weighted directed graph is -balanced if for every cut , the total weight of edges going from to $V\s…
Tight Lower Bounds on Graph Embedding Problems
Marek Cygan, Fedor V. Fomin, Alexander Golovnev +4
We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph to graph cannot be done in time . We al…
The Hardness of Subgraph Isomorphism
Marek Cygan, Jakub Pachocki, Arkadiusz Socała
Subgraph Isomorphism is a very basic graph problem, where given two graphs and one is to check whether is a subgraph of . Despite its simple definition, the Subgraph…
On the String Consensus Problem and the Manhattan Sequence Consensus Problem
Tomasz Kociumaka, Jakub W. Pachocki, Jakub Radoszewski +2
In the Manhattan Sequence Consensus problem (MSC problem) we are given integer sequences, each of length , and we are to find an integer sequence of length (called a…
Stretching Stretch
Michael B. Cohen, Gary L. Miller, Jakub W. Pachocki +2
We give a generalized definition of stretch that simplifies the efficient construction of low-stretch embeddings suitable for graph algorithms. The generalization, based on discoun…
Preconditioning in Expectation
Michael B. Cohen, Rasmus Kyng, Jakub W. Pachocki +2
We show that preconditioners constructed by random sampling can perform well without meeting the standard requirements of iterative methods. When applied to graph Laplacians, this…
A Note on Efficient Computation of All Abelian Periods in a String
Maxime Crochemore, Costas Iliopoulos, Tomasz Kociumaka +6
We derive a simple efficient algorithm for Abelian periods knowing all Abelian squares in a string. An efficient algorithm for the latter problem was given by Cummings and Smyth in…