Grigory Yaroslavtsev

Publication Activity (10 Years)

Years Active: 2009-2024
Publications (10 Years): 36

Top Topics

Sample Complexity

Hierarchical Clustering

Top Venues

Publications

Dmitrii Avdiukhin, Vaggos Chatziafratis, Konstantin Makarychev, Grigory Yaroslavtsev
Approximation Scheme for Weighted Metric Clustering via Sherali-Adams. AAAI (2024)
Noga Alon, Dmitrii Avdiukhin, Dor Elboim, Orr Fischer, Grigory Yaroslavtsev
Optimal Sample Complexity of Contrastive Learning. ICLR (2024)
Dmitrii Avdiukhin, Grigory Yaroslavtsev, Danny Vainstein, Orr Fischer, Sauman Das, Faraz Mirza
Tree Learning: Optimal Sample Complexity and Algorithms. AAAI (2023)
Dmitrii Avdiukhin, Grigory Yaroslavtsev, Danny Vainstein, Orr Fischer, Sauman Das, Faraz Mirza
Tree Learning: Optimal Algorithms and Sample Complexity. CoRR (2023)
Noga Alon, Dmitrii Avdiukhin, Dor Elboim, Orr Fischer, Grigory Yaroslavtsev
Optimal Sample Complexity of Contrastive Learning. CoRR (2023)
Dmitrii Avdiukhin, Grigory Yaroslavtsev
HOUDINI: Escaping from Moderately Constrained Saddles. IJCAI (2023)
Dmitrii Avdiukhin, Grigory Yaroslavtsev
HOUDINI: Escaping from Moderately Constrained Saddles. CoRR (2022)
Dmitrii Avdiukhin, Grigory Yaroslavtsev
Escaping Saddle Points with Compressed SGD. CoRR (2021)
Stanislav Naumov, Grigory Yaroslavtsev, Dmitrii Avdiukhin
Objective-Based Hierarchical Clustering of Deep Embedding Vectors. AAAI (2021)
Dmitrii Avdiukhin, Grigory Yaroslavtsev
Escaping Saddle Points with Compressed SGD. NeurIPS (2021)
Grigory Yaroslavtsev, Samson Zhou
Fast Fourier Sparsity Testing. SOSA (2020)
Vaggos Chatziafratis, Grigory Yaroslavtsev, Euiwoong Lee, Konstantin Makarychev, Sara Ahmadian, Alessandro Epasto, Mohammad Mahdian
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection. AISTATS (2020)
Grigory Yaroslavtsev, Samson Zhou, Dmitrii Avdiukhin
"Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack. AISTATS (2020)
Stanislav Naumov, Grigory Yaroslavtsev, Dmitrii Avdiukhin
Objective-Based Hierarchical Clustering of Deep Embedding Vectors. CoRR (2020)
Dmitrii Avdiukhin, Grigory Yaroslavtsev, Samson Zhou
"Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack. CoRR (2019)
Grigory Yaroslavtsev, Samson Zhou
Fast Fourier Sparsity Testing. CoRR (2019)
Dmitrii Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, Samson Zhou
Adversarially Robust Submodular Maximization under Knapsack Constraints. KDD (2019)
Grigory Yaroslavtsev, Samson Zhou
-Sketching of Valuation Functions. CoRR (2019)
Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto, Euiwoong Lee, Mohammad Mahdian, Konstantin Makarychev, Grigory Yaroslavtsev
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection. CoRR (2019)
Grigory Yaroslavtsev, Samson Zhou
-Sketching of Valuation Functions. APPROX-RANDOM (2019)
Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev
Hierarchical Clustering for Euclidean Data. AISTATS (2019)
Dmitrii Avdiukhin, Sergey Pupyrev, Grigory Yaroslavtsev
Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent. CoRR (2019)
Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev
Optimality of Linear Sketching Under Modular Updates. Computational Complexity Conference (2019)
Dmitrii Avdiukhin, Sergey Pupyrev, Grigory Yaroslavtsev
Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent. Proc. VLDB Endow. 12 (8) (2019)
Dmitrii Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, Samson Zhou
Adversarially Robust Submodular Maximization under Knapsack Constraints. CoRR (2019)
Sampath Kannan, Elchanan Mossel, Swagato Sanyal, Grigory Yaroslavtsev
Linear Sketching over F_2. Computational Complexity Conference (2018)
Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev
Optimality of Linear Sketching under Modular Updates. Electron. Colloquium Comput. Complex. 25 (2018)
Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev
Optimality of Linear Sketching under Modular Updates. CoRR (2018)
Grigory Yaroslavtsev, Adithya Vadapalli
Distances. ICML (2018)
Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev
Hierarchical Clustering for Euclidean Data. CoRR (2018)
Grigory Yaroslavtsev, Adithya Vadapalli
Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under $\ell_p$-Distances. CoRR (2017)
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev
Certifying Equality With Limited Interaction. Algorithmica 76 (3) (2016)
Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev
Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model. SODA (2016)
Sampath Kannan, Elchanan Mossel, Grigory Yaroslavtsev
Linear Sketching over $\mathbb F_2$. CoRR (2016)
Michael J. Kearns, Aaron Roth, Zhiwei Steven Wu, Grigory Yaroslavtsev
Private algorithms for the protected in social network search. Proc. Natl. Acad. Sci. USA 113 (4) (2016)
Elchanan Mossel, Sampath Kannan, Grigory Yaroslavtsev
. Electron. Colloquium Comput. Complex. 23 (2016)
Michael J. Kearns, Aaron Roth, Zhiwei Steven Wu, Grigory Yaroslavtsev
Privacy for the Protected (Only). CoRR (2015)
Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity. ICALP (1) (2015)
Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev
Tight Bounds for Linear Sketches of Approximate Matchings. CoRR (2015)
Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev
Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs. STOC (2015)
Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity. Electron. Colloquium Comput. Complex. 22 (2015)
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev
Parallel Algorithms for Geometric Graph Problems. CoRR (2014)
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev
Beyond set disjointness: the communication complexity of finding the intersection. PODC (2014)
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev
Parallel algorithms for geometric graph problems. STOC (2014)
Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, Grigory Yaroslavtsev
Private Analysis of Graph Structure. ACM Trans. Database Syst. 39 (3) (2014)
Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev
-testing. STOC (2014)
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
Steiner transitive-closure spanners of low-dimensional posets. Comb. 34 (3) (2014)
Grigory Yaroslavtsev
Going for Speed: Sublinear Algorithms for Dense r-CSPs. CoRR (2014)
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
Lower Bounds for Testing Properties of Functions over Hypergrid Domains. Computational Complexity Conference (2014)
Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev
Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs. CoRR (2014)
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev
Certifying Equality With Limited Interaction. APPROX-RANDOM (2014)
Nikhil R. Devanur, Konstantin Makarychev, Debmalya Panigrahi, Grigory Yaroslavtsev
Online Algorithms for Machine Minimization. CoRR (2014)
Grigory Yaroslavtsev, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava
Accurate and efficient private release of datacubes and contingency tables. ICDE (2013)
Sofya Raskhodnikova, Grigory Yaroslavtsev
-DNF and submodular functions. SODA (2013)
Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev
Approximation algorithms for spanner problems and Directed Steiner Forest. Inf. Comput. 222 (2013)
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
Lower Bounds for Testing Properties of Functions on Hypergrid Domains. Electron. Colloquium Comput. Complex. 20 (2013)
Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev
Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching. SODA (2013)
Piotr Berman, Grigory Yaroslavtsev
Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs. APPROX-RANDOM (2012)
Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, Grigory Yaroslavtsev
Accurate and Efficient Private Release of Datacubes and Contingency Tables CoRR (2012)
Sofya Raskhodnikova, Grigory Yaroslavtsev
Learning pseudo-Boolean k-DNF and Submodular Functions CoRR (2012)
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
Steiner Transitive-Closure Spanners of Low-Dimensional Posets. ICALP (1) (2011)
Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev
Improved Approximation for the Directed Spanner Problem. ICALP (1) (2011)
Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, Grigory Yaroslavtsev
Private Analysis of Graph Structure. Proc. VLDB Endow. 4 (11) (2011)
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
Steiner Transitive-Closure Spanners of d-Dimensional Posets CoRR (2010)
Evgeny Demenkov, Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev
New upper bounds on the Boolean circuit complexity of symmetric functions. Inf. Process. Lett. 110 (7) (2010)
Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev
Finding Efficient Circuits Using SAT-Solvers. SAT (2009)