38 citations · 152 across the 25 of their papers we have counts for
27 papers
Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
Arpit Agarwal, Sanjeev Khanna, Huan Li +4
We present a parallel algorithm for the -approximate maximum flow problem in capacitated, undirected graphs with vertices and edges, achieving $O(ε^{-3}\text{polylog…
Near-Optimal -Clustering in the Sliding Window Model
David P. Woodruff, Peilin Zhong, Samson Zhou
Clustering is an important technique for identifying structural information in large-scale data analysis, where the underlying dataset may be too large to store. In many applicatio…
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree
Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan +1
We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set of points, the goal i…
Differentially Private Clustering in Data Streams
Alessandro Epasto, Tamalika Mukherjee, Peilin Zhong
Clustering problems (such as -means and -median) are fundamental unsupervised machine learning primitives, and streaming clustering algorithms have been extensively studied i…
Measuring Re-identification Risk
CJ Carey, Travis Dick, Alessandro Epasto +8
Compact user representations (such as embeddings) form the backbone of personalization services. In this work, we present a new theoretical framework to measure re-identification r…
Differentially Private Continual Releases of Streaming Frequency Moment Estimations
Alessandro Epasto, Jieming Mao, Andres Munoz Medina +3
The streaming model of computation is a popular approach for working with large-scale data. In this setting, there is a stream of items and the goal is to compute the desired quant…
Stars: Tera-Scale Graph Building for Clustering and Graph Learning
CJ Carey, Jonathan Halcrow, Rajesh Jayaram +3
A fundamental procedure in the analysis of massive datasets is the construction of similarity graphs. Such graphs play a key role for many downstream tasks, including clustering, c…
Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank
Alessandro Epasto, Vahab Mirrokni, Bryan Perozzi +2
Personalized PageRank (PPR) is a fundamental tool in unsupervised learning of graph representations such as node ranking, labeling, and graph embedding. However, while data privacy…
Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni +1
Streaming computation plays an important role in large-scale data analysis. The sliding window model is a model of streaming computation which also captures the recency of the data…
Massively Parallel and Dynamic Algorithms for Minimum Size Clustering
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni +1
In this paper, we study the -gather problem, a natural formulation of minimum-size clustering in metric spaces. The goal of -gather is to partition points into clusters s…
Average Case Column Subset Selection for Entrywise -Norm Loss
Zhao Song, David P. Woodruff, Peilin Zhong
We study the column subset selection problem with respect to the entrywise -norm loss. It is known that in the worst case, to obtain a good rank- approximation to a matr…
Connected Components on a PRAM in Log Diameter Time
S. Cliff Liu, Robert E. Tarjan, Peilin Zhong
We present an -time randomized PRAM algorithm for computing the connected components of an -vertex, -edge undirected graph with maximum componen…
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
Alexandr Andoni, Clifford Stein, Peilin Zhong
We present a -approximate parallel algorithm for computing shortest paths in undirected graphs, achieving depth and $m\mathrm{poly}(\log n)…
Efficient Symmetric Norm Regression via Linear Sketching
Zhao Song, Ruosong Wang, Lin F. Yang +2
We provide efficient algorithms for overconstrained linear regression problems with size when the loss function is a symmetric norm (a norm invariant under sign-flips…
Streaming Balanced Clustering
Hossein Esfandiari, Vahab Mirrokni, Peilin Zhong
Clustering of data points in metric space is among the most fundamental problems in computer science with plenty of applications in data mining, information retrieval and machine l…
Log Diameter Rounds Algorithms for -Vertex and -Edge Connectivity
Alexandr Andoni, Clifford Stein, Peilin Zhong
Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarse-grained computation on large data --- da…
Enhancing Adversarial Defense by k-Winners-Take-All
Chang Xiao, Peilin Zhong, Changxi Zheng
We propose a simple change to existing neural network structures for better defending against gradient-based adversarial attacks. Instead of using popular activation functions (suc…
Rethinking Generative Mode Coverage: A Pointwise Guaranteed Approach
Peilin Zhong, Yuchen Mo, Chang Xiao +2
Many generative models have to combat . The conventional wisdom to this end is by reducing through training a statistical distance (such as -divergence)…
Towards a Zero-One Law for Column Subset Selection
Zhao Song, David P. Woodruff, Peilin Zhong
There are a number of approximation algorithms for NP-hard versions of low rank approximation, such as finding a rank- matrix minimizing the sum of absolute values of differ…
Subspace Embedding and Linear Regression with Orlicz Norm
Alexandr Andoni, Chengyu Lin, Ying Sheng +2
We consider a generalization of the classic linear regression problem to the case when the loss is an Orlicz norm. An Orlicz norm is parameterized by a non-negative convex function…
Parallel Graph Connectivity in Log Diameter Rounds
Alexandr Andoni, Clifford Stein, Zhao Song +2
We study graph connectivity problem in MPC model. On an undirected graph with nodes and edges, round connectivity algorithms have been known for over 35 years.…
BourGAN: Generative Networks with Metric Embeddings
Chang Xiao, Peilin Zhong, Changxi Zheng
This paper addresses the mode collapse for generative adversarial networks (GANs). We view modes as a geometric structure of data distribution in a metric space. Under this geometr…
Nearly Optimal Dynamic -Means Clustering for High-Dimensional Data
Wei Hu, Zhao Song, Lin F. Yang +1
We consider the -means clustering problem in the dynamic streaming setting, where points from a discrete Euclidean space can be dynamically inserted to o…
Relative Error Tensor Low Rank Approximation
Zhao Song, David P. Woodruff, Peilin Zhong
We consider relative error low rank approximation of with respect to the Frobenius norm: given an order- tensor , output a rank-$…