Publications

# Publications :: Search

## Show author

 Select a publication Show Title Venue Rating Date Journal article Grigory Yaroslavtsev, Adithya Vadapalli. Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under $\ell_p$-Distances. CoRR 2017, Volume 0 (0) 2017 Conference paper Sampath Kannan, Elchanan Mossel, Grigory Yaroslavtsev. Linear Sketching over $\mathbb F_2$. CoRR 2016, Volume 0 (0) 2016 Conference paper Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev. Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 2016 (0) 2016 Conference paper Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev. Certifying Equality With Limited Interaction. Algorithmica 2016, Volume 76 (0) 2016 Conference paper Elchanan Mossel, Sampath Kannan, Grigory Yaroslavtsev. Linear Sketching over ð??½ Electronic Colloquium on Computational Complexity (ECCC) 2016, Volume 23 (0) 2016 Conference paper Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev. Amplification of One-Way Information Complexity via Codes and Noise Sensitivity. Electronic Colloquium on Computational Complexity (ECCC) 2015, Volume 22 (0) 2015 Conference paper Shuchi Chawla 0001, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev. Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs. Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 2015 (0) 2015 Conference paper Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev. Amplification of One-Way Information Complexity via Codes and Noise Sensitivity. Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I 2015 (0) 2015 Journal article Michael J. Kearns, Aaron Roth, Zhiwei Steven Wu, Grigory Yaroslavtsev. Privacy for the Protected (Only). CoRR 2015, Volume 0 (0) 2015 Conference paper Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev. Tight Bounds for Linear Sketches of Approximate Matchings. CoRR 2015, Volume 0 (0) 2015 Journal article Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev. Parallel Algorithms for Geometric Graph Problems. CoRR 2014, Volume 0 (0) 2014 Journal article Nikhil R. Devanur, Konstantin Makarychev, Debmalya Panigrahi, Grigory Yaroslavtsev. Online Algorithms for Machine Minimization. CoRR 2014, Volume 0 (0) 2014 Conference paper Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev. L Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014 2014 (0) 2014 Conference paper Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014 2014 (0) 2014 Conference paper Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev. Steiner transitive-closure spanners of low-dimensional posets. Combinatorica 2014, Volume 34 (0) 2014 Conference paper Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev. Beyond set disjointness: the communication complexity of finding the intersection. ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014 2014 (0) 2014 Conference paper Grigory Yaroslavtsev. Going for Speed: Sublinear Algorithms for Dense r-CSPs. CoRR 2014, Volume 0 (0) 2014 Conference paper Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev. Certifying Equality With Limited Interaction. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain 2014 (0) 2014 Conference paper Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev. Lower Bounds for Testing Properties of Functions over Hypergrid Domains. IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014 2014 (0) 2014 Conference paper Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, Grigory Yaroslavtsev. Private Analysis of Graph Structure. ACM Trans. Database Syst. 2014, Volume 39 (0) 2014 Journal article Shuchi Chawla 0001, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev. Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs. CoRR 2014, Volume 0 (0) 2014 Journal article Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev. Approximation algorithms for spanner problems and Directed Steiner Forest. Inf. Comput. 2013, Volume 222 (0) 2013 Conference paper Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev. Lower Bounds for Testing Properties of Functions on Hypergrid Domains. Electronic Colloquium on Computational Complexity (ECCC) 2013, Volume 20 (0) 2013 Journal article David P. Woodruff, Grigory Yaroslavtsev. The Round Complexity of Small Set Intersection CoRR 2013, Volume 0 (0) 2013 Conference paper Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev. Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013 2013 (0) 2013