8 citations · 12 across the 5 of their papers we have counts for
5 papers
Tree Learning: Optimal Algorithms and Sample Complexity
Dmitrii Avdiukhin, Grigory Yaroslavtsev, Danny Vainstein +3
We study the problem of learning a hierarchical tree representation of data from labeled samples, taken from an arbitrary (and possibly adversarial) distribution. Consider a collec…
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…
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…
Online Algorithms for Machine Minimization
Nikhil Devanur, Konstantin Makarychev, Debmalya Panigrahi +1
In this paper, we consider the online version of the machine minimization problem (introduced by Chuzhoy et al., FOCS 2004), where the goal is to schedule a set of jobs with releas…