5 citations · 7 across the 3 of their papers we have counts for
8 papers
Novel Dense Subgraph Discovery Primitives: Risk Aversion and Exclusion Queries
Charalampos E. Tsourakakis, Tianyi Chen, Naonori Kakimura +1
In the densest subgraph problem, given a weighted undirected graph , with non-negative edge weights, we are asked to find a subset of nodes that maximizes…
Optimal lower bounds for universal relation, samplers, and finding duplicates
Jelani Nelson, Jakub Pachocki, Zhengyu Wang
In the communication problem (universal relation) [KRW95], Alice and Bob respectively receive and in with the promise that . The last pla…
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…
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…