Grigory Yaroslavtsev

Job Market: I am on the job market for industrial research and tenure-track faculty positions starting Fall'16.

Postdoctoral Fellow at the Warren Center for Network & Data Sciences at the departments of Computer and Information Sciences and Statistics at the Wharton School.

I am lucky to be mentored by Michael Kearns (CIS) and Elchanan Mossel (Stat) and collaborate with multiple other Warren Center faculty including Sampath Kannan, Sanjeev Khanna and Aaron Roth.

I am working on efficient algorithms for scalable data analysis including:

  • Approximation, distributed, streaming and online algorithms
  • Learning theory and property testing
  • Communication and information complexity
  • Data privacy and targeted alternatives to bulk data collection

This semester I am organizing the Theory Seminar. Recently created/taught/organized:


Papers (authors listed in alphabetical order unless otherwise specified)

Selected Publications

Other Publications



  • Fast Fourier Sparsity Testing over the Boolean Hypercube [Slides: (pptx), (pdf)]
    • University of Wisconsin, Madison. Theory Seminar. August 06, 2015.
  • Near Optimal LP Rounding for Correlation Clustering [ Video from MSR (link)] [Slides: (pptx), (pdf)]
    • Cornell University, Ithaca, NY. Theory Seminar. May 04, 2015.
    • MIT, Boston, MA. Algorithms and Complexity Seminar. April 09, 2015.
    • Microsoft Research, Redmond, WA. March 12, 2015.
    • Google Research, NYC. Google Tech Talk. February 17, 2015.
    • Rutgers University, New Brunswick, NJ. Theory Seminar. January 28, 2015.
    • Carnegie Mellon University, Pittsburgh, PA. Theory Lunch. January 21, 2015.
    • Pennsylvania State University, State College, PA. Departmental colloquium. January 20, 2015.
  • Lower Bounds for Testing Properties of Functions over Hypergrids [Slides: (pptx), (pdf)]
    • 29th IEEE Conference on Computational Complexity (CCC 2014), Vancouver, BC. June 13, 2014.
  • Beyond Set Disjointness: the Communication Complexity of Finding the Intersection [Slides: (pptx), (pdf)]
    • 33rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2014), Paris, France.
    • MIT, Boston, MA. Theory of Distributed Systems Seminar. May 16, 2014.
  • “The Big Data Theory” and Randomized Algorithms
    • Georgia Tech, Atlanta, GA. March 05, 2014.
  • Approximating Graph Problems: The Old and The New
    • Yahoo! Research, NYC. February 25, 2014.
    • MIT, Boston, MA. Algorithms and Complexity Seminar. February 19, 2014.
    • Toyota Technological Institute, Chicago, IL. February 17, 2014.
    • Brown University, Providence, RI. ICERM Theory Seminar. January 31, 2014.
  • Lp-Testing [Slides: (pptm), (pdf))]
    • Johns Hopkins University, Sublinear Algorithms Workshop. January 08, 2016.
    • Columbia University, Theory seminar. October 24, 2014.
    • 46th ACM Symposium on Theory of Computing (STOC 2014). June 01, 2014.
    • Microsoft Research, Redmond, Theory lunch. January 08, 2014.
    • Harvard University, Theory seminar. November 12, 2013.
    • Brown University, Providence, RI. Theory seminar. November 1, 2013.
    • IBM Almaden Research Center, San Jose, CA. Theory seminar. October 25, 2013.
  • Property Testing and Communication Complexity [Slides: (pptx), (pdf)]
    • MIT, Boston, MA. Algorithms and Complexity Seminar. September 11, 2013.
  • Accurate and Efficient Private Release of Datacubes and Contingency Tables
    • Cornell University, CDI project meeting. May 07, 2013. [Slides: (pptx), (pdf)]
    • 29th IEEE Inernational Conference on Data Engineering (ICDE 2013). April 10, 2013. [Slides: (pdf)]
  • Beating the Direct Sum Theorem in Communication Compelxity
    • Aarhus University, Denmark. Theory seminar. May 22, 2013.
    • MIT, Boston, MA. Algorithms and Complexity seminar. December 13, 2012.
    • Princeton University, Princeton, NJ. Theory lunch. November 16, 2012.
  • Overlapping Clustering with Qualitative Information
    • 53rd IEEE Symposium on Foundations of Computer Science (FOCS 2012). Poster session. October 22, 2012.
  • Parallel Algorithms for Geometric Problems [Slides: (pptx), (pdf)]
    • 22nd International Symposium on Mathematical Programming (ISMP 2015). July 15, 2015.
    • Johns Hopkins University, Baltimore, MD. Algoritms and Complexity Seminar. November 19, 2014.
    • University of Maryland, College Park, MD. Capital Area Theory Seminar. October 30, 2014.
    • University of Pennsylvania, Philadelphia, PA. Theory Seminar. August 29, 2014.
    • University of Massachusetts, Amherst, MA. Theory Seminar. May 19, 2014.
    • Google Research, NYC. Google Tech Talk. April 04, 2014.
    • Sandia Labs, Livermore, CA. March 27, 2014.
    • Stanford University, Stanford, CA. March 25, 2014.
    • Microsoft Research, SVC, Mountain View, CA. Lab meeting. October 17, 2012.
  • Learning and Testing Submodular Functions [ Video from MSR (link)][Slides: (pptx), (pdf)]
    • Microsoft Research, Redmond. Theory seminar. June 11, 2013.
    • University of Melbourne, Australia. Theory seminar. April 19, 2013.
    • UCLA, Los Angeles, CA. Theory seminar. February 04, 2013.
    • 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013). January 08, 2013.
    • Weizmann Institute of Science, Rehovot, Israel. December 30, 2012.
    • Harvard University, Boston, MA. Theory of Computing seminar. December 10, 2012.
    • Carnegie-Mellon University, Pittsburgh, PA. Theory Lunch. December 05, 2012.
    • Carnegie-Mellon University, Pittsburgh, PA. Tepper School of Business, Operations Research Seminar. December 07, 2012.
    • New York Computer Science and Economics Day 2012, Poster session. December 3, 2012.
    • IBM T.J. Watson Research Cetner, Yorktown Heights, NY. IP for Lunch. November 14, 2012.
    • Columbia University, NYC. Theory seminar. October 26, 2012.
    • 53rd IEEE Symposium on Foundations of Computer Science (FOCS 2012). Poster session. October 22, 2012.
    • Microsoft Research, Silicon Valley. Theory seminar. October 10, 2012.
    • EPFL, Lausanne, Switzerland. Algorithmic Frontiers Workshop, poster session. June 2012.
    • IBM Almaden Research Center, San Jose, CA. Theory seminar. May 2012.
    • 44th ACM Symposium on the Theory of Computing (STOC 2012). Poster session. May 2012.
  • Primal-dual Algorithms for Node-Weighted Network Design in Planar Graphs [Slides: (pptx), (pdf)]
    • 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2012). August 2012.
  • Advances in Directed Spanners [Slides: (pdf)].
    • University of Sydney, Australia. Theory seminar. April 9, 2013.
    • Carnegie-Mellon University, Theory Lunch, November 2011.
    • University of Maryland, Capital Area Theory Seminar, November 2011.
  • Private Analysis of Graph Structure [Slides: (pptx), (pdf)]
    • EPFL, Lausanne, Switzerland. Algorithmic Frontiers Workshop, poster session. June 2012. [Poster: (pdf)]
    • AT&T Labs --- Research, Florham Park, NJ. August 2011.
    • 37th International Conference on Very Large Data Bases (VLDB 2011), Research track. August 2011.
  • Improved Approximation for the Directed Spanner Problem [Slides: (pptx), (pdf)]
    • 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), Track A. July 2011. [Slides: (pptx)]
    • AT&T Labs --- Research, Florham Park, NJ. Mathematics Research Colloquium and Informal Seminar. June 2011.
    • 43rd ACM Symposium on the Theory of Computing (STOC 2011). Poster session. June 2011. [Poster: (pdf)]
    • Moscow State University. Combinatorial optimization seminar. May 2011.
    • IBM T.J. Watson Research Center, Yorktown Heights, NY. IP for lunch. April 2011.
    • St. Petersburg Institute of Fine Mechanics and Optics. Theory seminar. December 2010.
  • Steiner Transitive-Closure Spanners of Low-Dimensional Posets [Slides: (ppsx), (pdf)]
    • 38th International Colloquium on Automata, Languages and Programming (ICALP 2011),Track A. July 2011.
  • Linear Bounds on Circuit Complexity and Feebly One-Way Permutations [Slides: (pdf)]
    • Pennsylvania State University. Theory seminar. April 2010.



  • Algorithm competitions

    I participated in ACM ICPC and TopCoder competitions (as griffon) competing and setting problems in TopCoder Open Algorithms Finals.

  • Teaching algorithms for high-school students

    I was teaching advanced classes in algorithms for high-school students for ~5 years, coaching teams for algorithmic competitions. I participated in preparation of training camps and contests for Russian Olympiad in Informatics and International Olympiad in Informatics (both in Russia and in the U.S.).

  • Non-profit in education for high-school students: Homepage, Group on Vkontakte

    In 2009 I co-founded a non-profit organization focused on advanced extracurricular education in algorithms for high-school students (5 – 10 grades) in St. Petersburg, Russia. In 2013 it was expanded to Moscow and Yekaterinburg.

    In the early days we were supported by , and . Now donations are welcome!

  • Triathlon

    If I am not working then I am probably practicing for the next (more pictures). Let's do it together! ;)

    In 2015 I am participating in USAT Age Group National Championships in Olympic Distance and Ironman Lake Tahoe.

  • Software Engineering

    In 2007–2008 I was lucky to be a part of the FBReader team. This is an open source free e-Book Reader project.

    We developed the first version of FBReader for Android (now >5M downloads worldwide on Google play).

  • Very nerdy!

    There are some things I can't prove but rather just believe in. E.g. this logo I designed and proposed for the CSTheory website.

  • Education

    St. Petersburg Academic University is a unique center for continuous education in physics and engineering, run by Zhores Alferov, a Nobel Prize winner in Physics. In 8 years there I finished high school, B.S. and M.S. (a pilot class in theoretical computer science where I was the first student). I am forever grateful to all my teachers during those happy years!

    Here is a recent video (in Russian) about the new bachelors programs at the Academic University.


Graduate School and Academia