G. Yaroslavtsev

Most-cited papers

Private analysis of graph structure
Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, G. Yaroslavtsev
2011Proceedings of the VLDB Endowment313 citations Open access
Semantic Scholar
Parallel algorithms for geometric graph problems
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, G. Yaroslavtsev
2013Symposium on the Theory of Computing193 citations
Semantic Scholar
Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
Shuchi Chawla, K. Makarychev, T. Schramm, G. Yaroslavtsev
2014Symposium on the Theory of Computing146 citations Open access
Semantic Scholar
Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
Sepehr Assadi, S. Khanna, Yang Li, G. Yaroslavtsev
2016ACM-SIAM Symposium on Discrete Algorithms119 citations
Semantic Scholar
Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under $\ell_p$-Distances
G. Yaroslavtsev, Adithya Vadapalli
2017International Conference on Machine Learning56 citations
Semantic Scholar
Approximation algorithms for spanner problems and Directed Steiner Forest
P. Berman, Arnab Bhattacharyya, K. Makarychev, Sofya Raskhodnikova +1 more
2013Information and Computation54 citations Open access
Semantic Scholar
Lower Bounds for Testing Properties of Functions over Hypergrid Domains
Eric Blais, Sofya Raskhodnikova, G. Yaroslavtsev
2014Cybersecurity and Cyberforensics Conference52 citations
Semantic Scholar
Accurate and efficient private release of datacubes and contingency tables
G. Yaroslavtsev, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava
2012IEEE International Conference on Data Engineering52 citations
Semantic Scholar
Finding Efficient Circuits Using SAT-Solvers
Arist Kojevnikov, A. Kulikov, G. Yaroslavtsev
2009International Conference on Theory and Applications of Satisfiability Testing50 citations
Semantic Scholar
"Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack
Dmitrii Avdiukhin, G. Yaroslavtsev, Samson Zhou
2019International Conference on Artificial Intelligence and Statistics47 citations
Semantic Scholar
Lp-testing
P. Berman, Sofya Raskhodnikova, G. Yaroslavtsev
2014Symposium on the Theory of Computing45 citations
Semantic Scholar
Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
M. Molinaro, David P. Woodruff, G. Yaroslavtsev
2013ACM-SIAM Symposium on Discrete Algorithms41 citations
Semantic Scholar
Private algorithms for the protected in social network search
Michael Kearns, Aaron Roth, Zhiwei Steven Wu, G. Yaroslavtsev
2016Proceedings of the National Academy of Sciences of the United States of America38 citations Open access
Semantic Scholar
Hierarchical Clustering for Euclidean Data
M. Charikar, Vaggos Chatziafratis, Rad Niazadeh, G. Yaroslavtsev
2018International Conference on Artificial Intelligence and Statistics37 citations
Semantic Scholar
Beyond set disjointness: the communication complexity of finding the intersection
J. Brody, Amit Chakrabarti, R. Kondapally, David P. Woodruff +1 more
2014ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing36 citations
Semantic Scholar
Adversarially Robust Submodular Maximization under Knapsack Constraints
Dmitrii Avdiukhin, Slobodan Mitrovic, G. Yaroslavtsev, Samson Zhou
2019Knowledge Discovery and Data Mining35 citations Open access
Semantic Scholar
New upper bounds on the Boolean circuit complexity of symmetric functions
Evgeny Demenkov, Arist Kojevnikov, A. Kulikov, G. Yaroslavtsev
2010Information Processing Letters35 citations
Semantic Scholar
Improved Approximation for the Directed Spanner Problem
Piotr Berman, Arnab Bhattacharyya, K. Makarychev, Sofya Raskhodnikova +1 more
2011International Colloquium on Automata, Languages and Programming32 citations
Semantic Scholar
Objective-Based Hierarchical Clustering of Deep Embedding Vectors
Stanislav A. Naumov, G. Yaroslavtsev, Dmitrii Avdiukhin
2020AAAI Conference on Artificial Intelligence31 citations Open access
Semantic Scholar
Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under ` p Distances ( Appendicies )
G. Yaroslavtsev, Adithya Vadapalli
201828 citations
Semantic Scholar
Learning pseudo-Boolean k-DNF and submodular functions
Sofya Raskhodnikova, G. Yaroslavtsev
2012ACM-SIAM Symposium on Discrete Algorithms27 citations
Semantic Scholar
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
Vaggos Chatziafratis, G. Yaroslavtsev, Euiwoong Lee, K. Makarychev +3 more
2019International Conference on Artificial Intelligence and Statistics26 citations
Semantic Scholar
Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent
Dmitrii Avdiukhin, S. Pupyrev, G. Yaroslavtsev
2019Proceedings of the VLDB Endowment22 citations Open access
Semantic Scholar
Certifying Equality With Limited Interaction
J. Brody, Amit Chakrabarti, R. Kondapally, David P. Woodruff +1 more
2016Algorithmica20 citations
Semantic Scholar
Optimal Sample Complexity of Contrastive Learning
Noga Alon, Dmitrii Avdiukhin, Dor Elboim, Orr Fischer +1 more
2023International Conference on Learning Representations19 citations
Semantic Scholar
Linear Sketching over F_2
Sampath Kannan, Elchanan Mossel, Swagato Sanyal, G. Yaroslavtsev
2018Cybersecurity and Cyberforensics Conference17 citations
Semantic Scholar
Tight Bounds for Linear Sketches of Approximate Matchings
Sepehr Assadi, S. Khanna, Y. Li, G. Yaroslavtsev
2015arXiv.org17 citations
Semantic Scholar
Private Analysis of Graph Structure
Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, G. Yaroslavtsev
2014TODS17 citations Open access
Semantic Scholar
Online Algorithms for Machine Minimization
Nikhil R. Devanur, K. Makarychev, Debmalya Panigrahi, G. Yaroslavtsev
2014arXiv.org15 citations
Semantic Scholar
Optimality of linear sketching under modular updates
Kaave Hosseini, Shachar Lovett, G. Yaroslavtsev
2018Electron. Colloquium Comput. Complex.14 citations
Semantic Scholar
Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs
P. Berman, G. Yaroslavtsev
2012International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques14 citations
Semantic Scholar
Steiner transitive-closure spanners of low-dimensional posets
P. Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova +2 more
2010Comb.13 citations Open access
Semantic Scholar
Going for Speed: Sublinear Algorithms for Dense r-CSPs
G. Yaroslavtsev
2014arXiv.org9 citations
Semantic Scholar
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
M. Molinaro, David P. Woodruff, G. Yaroslavtsev
2015International Colloquium on Automata, Languages and Programming7 citations
Semantic Scholar
Privacy for the Protected (Only)
Michael Kearns, Aaron Roth, Zhiwei Steven Wu, G. Yaroslavtsev
2015arXiv.org6 citations
Semantic Scholar
Embedding Dimension of Contrastive Learning and k-Nearest Neighbors
Dmitrii Avdiukhin, Vaggos Chatziafratis, Orr Fischer, G. Yaroslavtsev
2024Neural Information Processing Systems5 citations
Semantic Scholar
Approximate F2-Sketching of Valuation Functions
G. Yaroslavtsev, Samson Zhou
2019International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques5 citations
Semantic Scholar
Escaping Saddle Points with Compressed SGD
Dmitrii Avdiukhin, G. Yaroslavtsev
2021Neural Information Processing Systems4 citations
Semantic Scholar
Linear Sketching over 𝔽2
Elchanan Mossel, Sampath Kannan, G. Yaroslavtsev
2016Electron. Colloquium Comput. Complex.4 citations
Semantic Scholar
Tree Learning: Optimal Sample Complexity and Algorithms
Dmitrii Avdiukhin, G. Yaroslavtsev, Danny Vainstein, O. Fischer +2 more
2023AAAI Conference on Artificial Intelligence3 citations Open access
Semantic Scholar
Fast Fourier Sparsity Testing
G. Yaroslavtsev, Samson Zhou
2019SIAM Symposium on Simplicity in Algorithms3 citations Open access
Semantic Scholar
Lower Bounds for Testing Properties of Functions on Hypergrid Domains
Eric Blais, Sofya Raskhodnikova, G. Yaroslavtsev
2013Electron. Colloquium Comput. Complex.3 citations
Semantic Scholar
Noise is All You Need: Private Second-Order Convergence of Noisy SGD
Dmitrii Avdiukhin, Michael Dinitz, Chenglin Fan, G. Yaroslavtsev
2024arXiv.org1 citations
Semantic Scholar
Linear Sketching over $\mathbb F_2$
Sampath Kannan, Elchanan Mossel, G. Yaroslavtsev
2016arXiv.org1 citations
Semantic Scholar
Certifying Equality With Limited Interaction
J. Brody, Amit Chakrabarti, R. Kondapally, David P. Woodruff +1 more
2016Algorithmica1 citations
Semantic Scholar
"efficient Combinatorial Methods in Sparsification, Summarization and Testing of Large Datasets"
G. Yaroslavtsev
20131 citations
Semantic Scholar
Steiner transitive-closure spanners of low-dimensional posets
P. Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova +2 more
2010Combinatorica1 citations Open access
Semantic Scholar
Approximation Scheme for Weighted Metric Clustering via Sherali-Adams
Dmitrii Avdiukhin, Vaggos Chatziafratis, K. Makarychev, G. Yaroslavtsev
2024AAAI Conference on Artificial Intelligence0 citations Open access
Semantic Scholar
Tree Learning: Optimal Algorithms and Sample Complexity
Dmitrii Avdiukhin, G. Yaroslavtsev, Danny Vainstein, O. Fischer +2 more
2023arXiv.org0 citations Open access
Semantic Scholar
HOUDINI: Escaping from Moderately Constrained Saddles
Dmitrii Avdiukhin, G. Yaroslavtsev
2022International Joint Conference on Artificial Intelligence0 citations Open access
Semantic Scholar