Grigory Yaroslavtsev

According to our database, Grigory Yaroslavtsev authored at least 48 papers between 2009 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Noise is All You Need: Private Second-Order Convergence of Noisy SGD.

Dmitrii Avdiukhin, Michael Dinitz, Chenglin Fan, Grigory Yaroslavtsev

CoRR, 2024

Optimal Sample Complexity of Contrastive Learning.

Noga Alon, Dmitrii Avdiukhin, Dor Elboim, Orr Fischer, Grigory Yaroslavtsev

Proceedings of the Twelfth International Conference on Learning Representations, 2024

Approximation Scheme for Weighted Metric Clustering via Sherali-Adams.

Dmitrii Avdiukhin, Vaggos Chatziafratis, Konstantin Makarychev, Grigory Yaroslavtsev

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

Tree Learning: Optimal Algorithms and Sample Complexity.

Dmitrii Avdiukhin, Grigory Yaroslavtsev, Danny Vainstein, Orr Fischer, Sauman Das, Faraz Mirza

CoRR, 2023

HOUDINI: Escaping from Moderately Constrained Saddles.

Dmitrii Avdiukhin, Grigory Yaroslavtsev

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

Tree Learning: Optimal Sample Complexity and Algorithms.

Dmitrii Avdiukhin, Grigory Yaroslavtsev, Danny Vainstein, Orr Fischer, Sauman Das, Faraz Mirza

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2021

Escaping Saddle Points with Compressed SGD.

Dmitrii Avdiukhin, Grigory Yaroslavtsev

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Objective-Based Hierarchical Clustering of Deep Embedding Vectors.

Stanislav Naumov, Grigory Yaroslavtsev, Dmitrii Avdiukhin

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020

Fast Fourier Sparsity Testing.

Grigory Yaroslavtsev, Samson Zhou

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

"Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack.

Grigory Yaroslavtsev, Samson Zhou, Dmitrii Avdiukhin

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection.

Vaggos Chatziafratis, Grigory Yaroslavtsev, Euiwoong Lee, Konstantin Makarychev, Sara Ahmadian, Alessandro Epasto, Mohammad Mahdian

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent.

Dmitrii Avdiukhin, Sergey Pupyrev, Grigory Yaroslavtsev

Proc. VLDB Endow., 2019

Adversarially Robust Submodular Maximization under Knapsack Constraints.

Dmitrii Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, Samson Zhou

Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019

Approximate F₂-Sketching of Valuation Functions.

Grigory Yaroslavtsev, Samson Zhou

Proceedings of the Approximation, 2019

Hierarchical Clustering for Euclidean Data.

Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev

Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

2018

Optimality of Linear Sketching under Modular Updates.

Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev

Electron. Colloquium Comput. Complex., 2018

Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under 𝓁_p Distances.

Grigory Yaroslavtsev, Adithya Vadapalli

Proceedings of the 35th International Conference on Machine Learning, 2018

Linear Sketching over F_2.

Sampath Kannan, Elchanan Mossel, Swagato Sanyal, Grigory Yaroslavtsev

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under $\ell_p$-Distances.

Grigory Yaroslavtsev, Adithya Vadapalli

CoRR, 2017

2016

Private algorithms for the protected in social network search.

Michael J. Kearns, Aaron Roth, Zhiwei Steven Wu, Grigory Yaroslavtsev

Proc. Natl. Acad. Sci. USA, 2016

Linear Sketching over 𝔽₂.

Elchanan Mossel, Sampath Kannan, Grigory Yaroslavtsev

Electron. Colloquium Comput. Complex., 2016

Linear Sketching over $\mathbb F_2$.

Sampath Kannan, Elchanan Mossel, Grigory Yaroslavtsev

CoRR, 2016

Certifying Equality With Limited Interaction.

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev

Algorithmica, 2016

Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model.

Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Amplification of One-Way Information Complexity via Codes and Noise Sensitivity.

Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev

Electron. Colloquium Comput. Complex., 2015

Privacy for the Protected (Only).

Michael J. Kearns, Aaron Roth, Zhiwei Steven Wu, Grigory Yaroslavtsev

CoRR, 2015

Tight Bounds for Linear Sketches of Approximate Matchings.

Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev

CoRR, 2015

Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs.

Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

Going for Speed: Sublinear Algorithms for Dense r-CSPs.

Grigory Yaroslavtsev

CoRR, 2014

Online Algorithms for Machine Minimization.

Nikhil R. Devanur, Konstantin Makarychev, Debmalya Panigrahi, Grigory Yaroslavtsev

CoRR, 2014

Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs.

Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev

CoRR, 2014

Steiner transitive-closure spanners of low-dimensional posets.

Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev

Comb., 2014

L_p-testing.

Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev

Proceedings of the Symposium on Theory of Computing, 2014

Parallel algorithms for geometric graph problems.

Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev

Proceedings of the Symposium on Theory of Computing, 2014

Beyond set disjointness: the communication complexity of finding the intersection.

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Lower Bounds for Testing Properties of Functions over Hypergrid Domains.

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Approximation algorithms for spanner problems and Directed Steiner Forest.

Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev

Inf. Comput., 2013

Lower Bounds for Testing Properties of Functions on Hypergrid Domains.

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

Electron. Colloquium Comput. Complex., 2013

Learning pseudo-Boolean <i>k</i>-DNF and submodular functions.

Sofya Raskhodnikova, Grigory Yaroslavtsev

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching.

Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Accurate and efficient private release of datacubes and contingency tables.

Grigory Yaroslavtsev, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava

Proceedings of the 29th IEEE International Conference on Data Engineering, 2013

2012

Learning pseudo-Boolean k-DNF and Submodular Functions

Sofya Raskhodnikova, Grigory Yaroslavtsev

CoRR, 2012

Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs.

Piotr Berman, Grigory Yaroslavtsev

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Private Analysis of Graph Structure.

Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, Grigory Yaroslavtsev

Proc. VLDB Endow., 2011

Improved Approximation for the Directed Spanner Problem.

Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

New upper bounds on the Boolean circuit complexity of symmetric functions.

Evgeny Demenkov, Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev

Inf. Process. Lett., 2010

Steiner Transitive-Closure Spanners of d-Dimensional Posets

Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev

CoRR, 2010

2009

Finding Efficient Circuits Using SAT-Solvers.

Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev

Proceedings of the Theory and Applications of Satisfiability Testing, 2009