21 citations · 94 across the 25 of their papers we have counts for
15 papers · 1 filter
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto +4
Hierarchical Clustering is an unsupervised data analysis method which has been widely used for decades. Despite its popularity, it had an underdeveloped analytical foundation and t…
Fast Fourier Sparsity Testing
Grigory Yaroslavtsev, Samson Zhou
A function is -sparse if it has at most non-zero Fourier coefficients. Motivated by applications to fast sparse Fourier transforms over $…
"Bring Your Own Greedy"+Max: Near-Optimal -Approximations for Submodular Knapsack
Dmitrii Avdiukhin, Grigory Yaroslavtsev, Samson Zhou
The problem of selecting a small-size representative summary of a large dataset is a cornerstone of machine learning, optimization and data science. Motivated by applications to re…
Approximate -Sketching of Valuation Functions
Grigory Yaroslavtsev, Samson Zhou
We study the problem of constructing a linear sketch of minimum dimension that allows approximation of a given real-valued function …
Adversarially Robust Submodular Maximization under Knapsack Constraints
Dmitrii Avdiukhin, Slobodan Mitrović, Grigory Yaroslavtsev +1
We propose the first adversarially robust algorithm for monotone submodular maximization under single and multiple knapsack constraints with scalable implementations in distributed…
Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent
Dmitrii Avdiukhin, Sergey Pupyrev, Grigory Yaroslavtsev
Motivated by performance optimization of large-scale graph processing systems that distribute the graph across multiple machines, we consider the balanced graph partitioning proble…
Hierarchical Clustering for Euclidean Data
Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh +1
Recent works on Hierarchical Clustering (HC), a well-studied problem in exploratory data analysis, have focused on optimizing various objective functions for this problem under arb…
Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under -Distances
Grigory Yaroslavtsev, Adithya Vadapalli
We present massively parallel (MPC) algorithms and hardness of approximation results for computing Single-Linkage Clustering of input -dimensional vectors under Hamming, $\e…
Linear Sketching over
Sampath Kannan, Elchanan Mossel, Grigory Yaroslavtsev
We initiate a systematic study of linear sketching over . For a given Boolean function a randomized -sketch is a distribu…
Privacy for the Protected (Only)
Michael Kearns, Aaron Roth, Zhiwei Steven Wu +1
Motivated by tensions between data privacy for individual citizens, and societal priorities such as counterterrorism and the containment of infectious disease, we introduce a compu…
Tight Bounds for Linear Sketches of Approximate Matchings
Sepehr Assadi, Sanjeev Khanna, Yang Li +1
We resolve the space complexity of linear sketches for approximating the maximum matching problem in dynamic graph streams where the stream may include both edge insertion and dele…
Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs
Shuchi Chawla, Konstantin Makarychev, Tselil Schramm +1
We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality g…
Going for Speed: Sublinear Algorithms for Dense r-CSPs
Grigory Yaroslavtsev
We give new sublinear and parallel algorithms for the extensively studied problem of approximating n-variable r-CSPs (constraint satisfaction problems with constraints of arity r u…
Parallel Algorithms for Geometric Graph Problems
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak +1
We give algorithms for geometric graph problems in the modern parallel models inspired by MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points i…
Steiner Transitive-Closure Spanners of d-Dimensional Posets
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu +3
Given a directed graph G and an integer k >= 1, a k-transitive-closure-spanner (k-TCspanner) of G is a directed graph H that has (1) the same transitive-closure as G and (2) diamet…