Finding Efficient Circuits Using SAT-Solvers. - Arist Kojevnikov; Alexander S. Kulikov; Grigory Yaroslavtsev (SAT, 2009)

Steiner Transitive-Closure Spanners of d-Dimensional Posets - Piotr Berman; Arnab Bhattacharyya 001; Elena Grigorescu; Sofya Raskhodnikova; David P. Woodruff; Grigory Yaroslavtsev (CoRR, 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)

Improved Approximation for the Directed Spanner Problem. - Piotr Berman; Arnab Bhattacharyya 001; Konstantin Makarychev; Sofya Raskhodnikova; Grigory Yaroslavtsev (ICALP (1), 2011)

Private Analysis of Graph Structure. - Vishesh Karwa; Sofya Raskhodnikova; Adam D. Smith 001; Grigory Yaroslavtsev (Proc. VLDB Endow., 2011)

Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs. - Piotr Berman; Grigory Yaroslavtsev (APPROX-RANDOM, 2012)

Learning pseudo-Boolean k-DNF and Submodular Functions - Sofya Raskhodnikova; Grigory Yaroslavtsev (CoRR, 2012)

Accurate and efficient private release of datacubes and contingency tables. - Grigory Yaroslavtsev; Graham Cormode; Cecilia M. Procopiuc; Divesh Srivastava (ICDE, 2013)

Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching. - Marco Molinaro 001; David P. Woodruff; Grigory Yaroslavtsev (SODA, 2013)

Learning pseudo-Boolean k-DNF and submodular functions. - Sofya Raskhodnikova; Grigory Yaroslavtsev (SODA, 2013)

Lower Bounds for Testing Properties of Functions on Hypergrid Domains. - Eric Blais; Sofya Raskhodnikova; Grigory Yaroslavtsev (Electron. Colloquium Comput. Complex., 2013)

Approximation algorithms for spanner problems and Directed Steiner Forest. - Piotr Berman; Arnab Bhattacharyya 001; Konstantin Makarychev; Sofya Raskhodnikova; Grigory Yaroslavtsev (Inf. Comput., 2013)

Lower Bounds for Testing Properties of Functions over Hypergrid Domains. - Eric Blais; Sofya Raskhodnikova; Grigory Yaroslavtsev (CCC, 2014)

Beyond set disjointness: the communication complexity of finding the intersection. - Joshua Brody; Amit Chakrabarti; Ranganath Kondapally; David P. Woodruff; Grigory Yaroslavtsev (PODC, 2014)

Parallel algorithms for geometric graph problems. - Alexandr Andoni; Aleksandar Nikolov; Krzysztof Onak; Grigory Yaroslavtsev (STOC, 2014)

Lp-testing. - Piotr Berman; Sofya Raskhodnikova; Grigory Yaroslavtsev (STOC, 2014)

Steiner transitive-closure spanners of low-dimensional posets. - Piotr Berman; Arnab Bhattacharyya 001; Elena Grigorescu; Sofya Raskhodnikova; David P. Woodruff; Grigory Yaroslavtsev (Comb., 2014)

Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs. - Shuchi Chawla 001; Konstantin Makarychev; Tselil Schramm; Grigory Yaroslavtsev (CoRR, 2014)

Online Algorithms for Machine Minimization. - Nikhil R. Devanur; Konstantin Makarychev; Debmalya Panigrahi; Grigory Yaroslavtsev (CoRR, 2014)

Going for Speed: Sublinear Algorithms for Dense r-CSPs. - Grigory Yaroslavtsev (CoRR, 2014)

Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs. - Shuchi Chawla 001; Konstantin Makarychev; Tselil Schramm; Grigory Yaroslavtsev (STOC, 2015)

Tight Bounds for Linear Sketches of Approximate Matchings. - Sepehr Assadi; Sanjeev Khanna; Yang Li 025; Grigory Yaroslavtsev (CoRR, 2015)

Privacy for the Protected (Only). - Michael J. Kearns; Aaron Roth 001; Zhiwei Steven Wu; Grigory Yaroslavtsev (CoRR, 2015)

Amplification of One-Way Information Complexity via Codes and Noise Sensitivity. - Marco Molinaro 001; David P. Woodruff; Grigory Yaroslavtsev (Electron. Colloquium Comput. Complex., 2015)

Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model. - Sepehr Assadi; Sanjeev Khanna; Yang Li 025; Grigory Yaroslavtsev (SODA, 2016)

Certifying Equality With Limited Interaction. - Joshua Brody; Amit Chakrabarti; Ranganath Kondapally; David P. Woodruff; Grigory Yaroslavtsev (Algorithmica, 2016)

Linear Sketching over $ mathbb F_2$. - Sampath Kannan; Elchanan Mossel; Grigory Yaroslavtsev (CoRR, 2016)

Linear Sketching over 𝔽2. - Elchanan Mossel; Sampath Kannan; Grigory Yaroslavtsev (Electron. Colloquium Comput. Complex., 2016)

Private algorithms for the protected in social network search. - Michael J. Kearns; Aaron Roth 001; Zhiwei Steven Wu; Grigory Yaroslavtsev (Proc. Natl. Acad. Sci. USA, 2016)

Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under $ ell_p$-Distances. - Grigory Yaroslavtsev; Adithya Vadapalli (CoRR, 2017)

Linear Sketching over F_2. - Sampath Kannan; Elchanan Mossel; Swagato Sanyal; Grigory Yaroslavtsev (CCC, 2018)

Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under 𝓁p Distances. - Grigory Yaroslavtsev; Adithya Vadapalli (ICML, 2018)

Optimality of Linear Sketching under Modular Updates. - Kaave Hosseini; Shachar Lovett; Grigory Yaroslavtsev (Electron. Colloquium Comput. Complex., 2018)

Hierarchical Clustering for Euclidean Data. - Moses Charikar; Vaggos Chatziafratis; Rad Niazadeh; Grigory Yaroslavtsev (AISTATS, 2019)

Approximate F2-Sketching of Valuation Functions. - Grigory Yaroslavtsev; Samson Zhou (APPROX-RANDOM, 2019)

Adversarially Robust Submodular Maximization under Knapsack Constraints. - Dmitrii Avdiukhin; Slobodan Mitrovic; Grigory Yaroslavtsev; Samson Zhou (KDD, 2019)

Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent. - Dmitrii Avdiukhin; Sergey Pupyrev; Grigory Yaroslavtsev (Proc. VLDB Endow., 2019)

Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection. - Vaggos Chatziafratis; Grigory Yaroslavtsev; Euiwoong Lee; Konstantin Makarychev; Sara Ahmadian; Alessandro Epasto; Mohammad Mahdian (AISTATS, 2020)

"Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack. - Grigory Yaroslavtsev; Samson Zhou; Dmitrii Avdiukhin (AISTATS, 2020)

Fast Fourier Sparsity Testing. - Grigory Yaroslavtsev; Samson Zhou (SOSA, 2020)

Objective-Based Hierarchical Clustering of Deep Embedding Vectors. - Stanislav Naumov; Grigory Yaroslavtsev; Dmitrii Avdiukhin (AAAI, 2021)

Escaping Saddle Points with Compressed SGD. - Dmitrii Avdiukhin; Grigory Yaroslavtsev (NeurIPS, 2021)

Tree Learning: Optimal Sample Complexity and Algorithms. - Dmitrii Avdiukhin; Grigory Yaroslavtsev; Danny Vainstein; Orr Fischer; Sauman Das; Faraz Mirza (AAAI, 2023)

HOUDINI: Escaping from Moderately Constrained Saddles. - Dmitrii Avdiukhin; Grigory Yaroslavtsev (IJCAI, 2023)

Tree Learning: Optimal Algorithms and Sample Complexity. - Dmitrii Avdiukhin; Grigory Yaroslavtsev; Danny Vainstein; Orr Fischer; Sauman Das; Faraz Mirza (CoRR, 2023)

Approximation Scheme for Weighted Metric Clustering via Sherali-Adams. - Dmitrii Avdiukhin; Vaggos Chatziafratis; Konstantin Makarychev; Grigory Yaroslavtsev (AAAI, 2024)

Optimal Sample Complexity of Contrastive Learning. - Noga Alon; Dmitrii Avdiukhin; Dor Elboim; Orr Fischer; Grigory Yaroslavtsev (ICLR, 2024)

Embedding Dimension of Contrastive Learning and k-Nearest Neighbors. - Dmitrii Avdiukhin; Vaggos Chatziafratis; Orr Fischer; Grigory Yaroslavtsev (NeurIPS, 2024)

Noise is All You Need: Private Second-Order Convergence of Noisy SGD. - Dmitrii Avdiukhin; Michael Dinitz; Chenglin Fan; Grigory Yaroslavtsev (CoRR, 2024)