Grigory Yaroslavtsev

68 papers A* 17A 7Journal 37Unranked 7

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