I am currently focused on a stealth project and am away from academia. Previously I was an assistant professor of Computer Science at George Mason, based in Washington, DC metro area. Group and alumni placements are here, check also highlights, wiki, papers, personal and diversity.

grigory@grigory.us Wikipedia Blog Scholar GitHub LinkedIn Facebook X Quora YouTube channel Download CV

Previous Next

Artificial Intelligence

Representation Learning Provable guarantees for learning hierarchical representations from labeled samples and deep embeddings.

Optimization Provable guarantees for distributed and constrained non-convex optimization.

Hierarchical Clustering

Graph Partitioning Multi-dimensional balanced graph partitioning algorithms for Facebook graphs using projected gradient descent.

Clustering Vector Data Projection-based algorithms for hierarchical clustering of high-dimensional vector data.

Massively Parallel Computation

Theoretical model Model for MapReduce/Spark-like computation. Algorthms for vector data: min spanning tree, min-cost bichromatic matching.

Single-Linkage Clustering Scalable massively parallel algorithms for single-linkage clustering of vector data.

Private Data Analysis

Private Targeted Search Algorithms for searching for targeted individuals in networks with privacy guarantees for protected subpopulations.

Private Graph Statistics Algorithms for releasing subgraph statistics about large networks while preserving privacy of relationships.

Publications:

• AI/ML/DB/DM/Stat conferences: AAAI, AISTATS, ICDE, ICLR, ICML, IJCAI, KDD, NeurIPS, OPT@NeurIPS, VLDB.
• TCS conferences: APPROX, CCC, ICALP, PODC, RANDOM, SAT, SODA, SOSA@SODA, STOC.
• Journals: Algorithmica, Combinatorica, I&C, IPL, PNAS, TODS.

(Senior) Program committees:

• AI/ML: AAAI ('20–'24), AISTATS ('19–'24), NeurIPS ('16–'24), IJCAI SPC ('21,'23), ICML ('18–'24), ICLR ('18–'24), UAI ('19,'22).
• TCS: SODA 21, APPROX 18, BeyondMR 18, COCOON 17, SODA 17, ESA 16, SOFSEM 15.

Group and Alumni

• Samson Zhou: Postdoc, '18–'19 → Postdoc, CMU
• Dmitrii Avdiukhin: PhD, '17–'23 → McCormick Fellow, Northwestern
• Sauman Das, TJHSST: High School Intern, S'22 → Undegrad, UPenn
• Faraz Mirza, TJHSST: High School Intern, S'22 → Undergrad, CMU
• Farid Arthaud, ENS Paris: Undegrad Intern, S'19 → PhD, MIT
• Jakub Boguta, U. Warsaw: Undergrad Intern, S'19 →
• Stanislav Naumov, SPb ITMO U.: Undergrad Intern, F'19 → CEO, Topflow

Organizer:

• Recent Trends in Clustering and Classification: 3-day workshop at TTI-Chicago, '19.
• Linear Sketching as a Tool for Everything: 1-day workshop at FOCS'17.
• 67th Midwest Theory Day: 2-day workshop at Indiana University, Bloomington, '17.
• Big Data Through the Lens of Sublinear Algorithms: 2-day workshop at Rutgers DIMACS, '15.
• Algorithmic Frontiers of Modern Massively Parallel Computation: 1-day workshop at ACM FCRC '15.
• Sublinear Algorithms and Big Data Day: Sublinear Day #1 (Brown '14), Sublinear Day #2 (MIT '15).

• '21 – '24. Assistant Professor, GMU CS.
  • F'23. Visiting Faculty, Stanford, CA.
• '20 – '21. Lead ML Engineer, Lunchclub.
• '16 – '20. Assistant Professor, IUB CS.
  • S'19. Alan Turing Institute, London, UK.
• '14 – '16. Warren Center Fellow, UPenn CIS and Wharton Statistics.
• '13 – '14. Institute Fellow, Brown ICERM.
• '10 – '13. Ph.D., Penn State CSE.
  • S'13 Intern. Microsoft Research, WA.
  • F'12 Intern. Microsoft Research, CA.
  • S'12 Intern. IBM Research, CA.
  • S'11 Intern. AT&T Research, NJ.

Achievements and Awards

• Facebook Faculty Research Award, '17.
• NSF CRII Award, '17.
• Warren Center Fellow, UPenn, '14-'16.
• ICERM Institute Fellow, Brown, '13-'14.
• Graduate Research Award, Penn St. CSE, '12.
• College of Eng. Fellow, Penn St., '10-'13.
• University Graduate Fellow, Penn St., '10-'11.
• TopCoder Open Algorithm (Top-24), '10.

Teaching

• S'24: CS630 Advanced Algorithms @ GMU
• F'23: CS583 Analysis of Algorithms @ GMU
• S'23: CS583 Analysis of Algorithms @ GMU
• F'22: CS583 Analysis of Algorithms @ GMU
• S'22: CS630 Advanced Algorithms @ GMU
• F'21: CS583 Analysis of Algorithms @ GMU
• S'20: B505 Applied Algorithms @ IUB
• F'19: B505 Applied Algorithms @ IUB
• S'19: H343 Data Structures (honors) @ IUB
• F'18: C343 Data Structures @ IUB
• S'18: H343 Data Structures (honors) @ IUB
• F'17: B505 Applied Algorithms @ IUB (with Funda Ergun)
• F'17: B609 Foundations of Data Science @ IUB
• F'16: B609 Foundations of Data Science @ IUB
• F'15: CIS 700 algorithms for Big Data @ Penn
• S'15: CIS 625 Computational Learning Theory @ Penn (with Michael Kearns)

Papers (alphabetical order unless marked with^*)

Selected Publications

Embedding Dimension of Contrastive Learning and k-Nearest Neighbors
D. Avdiukhin, V. Chatziafratis, O. Fischer, G. Yaroslavtsev
NeurIPS 2024 (38th Conference on Neural Information Processing Systems)

Optimal Sample Complexity of Contrastive Learning
N. Alon, D. Avdiukhin, D. Elboim, O. Fischer, G. Yaroslavtsev
ICLR 2024 (12th International Conference on Learning Representations). Spotlight (5% acceptance rate).

HOUDINI: Escaping from Moderately Constrained Saddles
D. Avdiukhin, G. Yaroslavtsev
IJCAI 2023 (32nd International Joint Conference on Artificial Intelligence).
OPT@NeurIPS 2022 (14th OPT Workshop on Optimization for Machine Learning).

Tree Learning: Optimal Sample Complexity and Algorithms
D. Avdiukhin, G. Yaroslavtsev^*, D. Vainstein, O. Fischer, S. Das, F. Mirza
AAAI 2023 (37th AAAI Conference on Artificial Intelligence).

Escaping Saddle Points with Compressed SGD
D. Avdiukhin, G. Yaroslavtsev
NeurIPS 2021 (35th Conference on Neural Information Processing Systems).

Objective-Based Hierarchical Clustering of Deep Embedding Vectors
S. Naumov, G. Yaroslavtsev^*, D. Avdiukhin
AAAI 2021 (35th AAAI Conference on Artificial Intelligence).

Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent
D. Avdiukhin, S. Pupyrev, G. Yaroslavtsev
VLDB 2019, Research track (45th International Conference on Very Large Data Bases).

Hierarchical Clustering for Euclidean Data
M. Charikar, V. Chatziafratis, R. Niazadeh, G. Yaroslavtsev
AISTATS 2019 (22nd International Conference on Artificial Intelligence and Statistics).

Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under ℓ_p-Distances
G. Yaroslavtsev^*, A. Vadapalli
ICML 2018 (35th International Conference on Machine Learning). Long talk (8.6% acceptance rate).
Code on Github (by Adithya Vadapalli).

Linear Sketching over F₂
S. Kannan, E. Mossel, S. Sanyal, G. Yaroslavtsev
CCC 2018 (33rd Conference on Computational Complexity).
Blog post on “The Big Data Theory”.

Private Algorithms for the Protected in Social Network Search
M. Kearns, A. Roth, S. Wu, G. Yaroslavtsev
PNAS 2016 (Proceedings of the National Academy of Sciences), via direct submission.
Spotlight story on the Penn front page: Balancing Privacy and Security in Network Analysis.
External media coverage: PBS Newshour, ACM Tech News / The Daily Pennsylvanian, Schneier on Security, AAU, Quartz, Pacific Standard, Wired (German), The Naked Scientists Podcast and Vice Motherboard.

Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs
S. Chawla, K. Makarychev, T. Schramm, G. Yaroslavtsev
STOC 2015 (47th ACM Symposium on the Theory of Computing).
See the Wikipedia article on correlation clustering for more details.
For applications in data mining see a Yahoo! KDD'14 tutorial by Francesco Bonchi, David Garcia-Soriano and Edo Liberty.

L_p-Testing
P. Berman, S. Raskhodnikova, G. Yaroslavtsev
STOC 2014 (46th ACM Symposium on the Theory of Computing).
Simple introduction by Sofya Raskhodnikova in the Encyclopedia of Algorithms (Springer).
Open problems from JHU workshop on Sublinear Algorithms [pptx, pdf].
Oded Goldreich's review on “My Choices”. Property Testing Review Post 1, Post 2.

Parallel Algorithms for Geometric Graph Problems
A. Andoni, A. Nikolov, K. Onak, G. Yaroslavtsev
STOC 2014 (46th ACM Symposium on the Theory of Computing).
Notes by Thomas Steinke from Jelani Nelson's Algorithms for Big Data Course at Harvard
Notes by Kui Tang from Alex Andoni's Algorithmic Techniques for Massive Data Course at Columbia.

Private Analysis of Graph Structure
V. Karwa, S. Raskhodnikova, A. Smith, G. Yaroslavtsev
VLDB 2011, Research track (37th International Conference on Very Large Data Bases).
Full version in ACM Transactions on Database Systems.

Approximation Algorithms for Spanner Problems and Directed Steiner Forest
P. Berman, A. Bhattacharyya, K. Makarychev, S. Raskhodnikova, G. Yaroslavtsev
ICALP 2011, Track A (38th International Colloquium on Automata, Languages and Programming), special issue of “Information and Computation”.
Runner-up for the Best Paper Award.
Open Problem #2 from the Princeton Workshop on Approximation Algorithms. See also my slides.

Finding Efficient Circuits Using SAT-solvers
A. Kojevnikov, A. Kulikov, G. Yaroslavtsev
SAT 2009 (12th International Conference on Theory and Applications of Satisfiability Testing).
Cited multiple times in Volume 4B of Donald E. Knuth's “The Art of Computer Programming”.
Notes by Ryan Williams from his class Topics in Circuit Complexity at Stanford.
Extension in Information Processing Letters as E.Demenkov, A.Kojevnikov, A.Kulikov, G.Yaroslavtsev “New upper bounds on the Boolean Circuit Complexity of Symmetric Functions” [Full text: (pdf)]

Other Publications

^* Indicates papers with non-alphabetical ordering of authors.

Preprints

• I've been teaching CSCI-H343 (Data Structures, honors) at Indiana University, Bloomington in Spring 2018.
• I've been teaching CSCI-B505 (Applied Algorithms) at Indiana University, Bloomington in Fall 2017.
• Short tutorial Clustering on Clusters: Massively Parallel Algorithms for Clustering Graphs and Vectors at Facebook, Menlo Park, CA, Spring 2017.
• I have developed CSCI-B609, Foundations of Data Science (graduate) at Indiana University, Bloomington, Fall 2016 and Fall 2017.
• Guest lecturer at CIS 399, Foundations of Data Science (undergraduate) at the University of Pennsylvania, Spring 2016.
  • Massively Parallel Algorithms. Slides (pdf).
• I have developed CIS 700, Algorithms for Big Data (graduate) at the University of Pennsylvania, Fall 2015.
• Co-teaching CIS 625, Computational Learning Theory (graduate, together with Michael Kearns) at the University of Pennsylvania, Spring 2015.
  • Lecture 1: Fourier Analysis and Learning, Part 1. Slides (pdf).
  • Lecture 2: Fourier Analysis and Learning, Part 2. Slides (pdf).
  • Lecture 3: Learning Submodular Functions. Slides (pdf).
  • Lecture 4: L_p-Testing. Slides (pdf).
• I have developed Sublinear Algorithms for Big Data: 15-hour crash course at the University of Buenos Aires, July 2014.
• Guest lecturer at CMPSC 464, Introduction to the Theory of Computation (undergraduate) at Pennsylvania State University, Fall 2010.

• 

  Triathlon and Duathlon

  I caught the triathlon bug while interning at IBM and Microsoft Research in Bay area in 2012. Since then if I am not working then I am probably practicing for the next year's (old pictures). 5xIM so far: Woodlands, TX (2013), Lake Tahoe, CA (2014 cancelled -> 2015), Lake Placid, NY (2016), Santa Rosa, CA (2017), Cairns, AUS (2018). Let's do it together! ;)

  In 2017 I was representing Team USA in the M30-34 age group at the ITU Standard Distance Duathlon World Championship in Penticton, Canada. In 2019 I was representing Team USA in the M30-34 age group at the ITU Long Distance Triathlon World Championship in Pontevedra, Spain.

• 

  Algorithms competitions

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

  After making it to the TopCoder Algorithms Finals 2010 in Las Vegas (Top-24 worldwide individually), I retired from competitive programming to focus on research and triathlon.

• 

  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 the Russian Olympiad in Informatics and the International Olympiad in Informatics (both in Russia and in the U.S.).

  My proudest accomplishments as a coach are leading my high-school team to a victory in St. Petersburg Olympiad in Informatics in 2008-2009 and the fact that our sloppy coaching didn't stop Team USA from earning a bunch of medals in 2011.

• 

  Non-profit in education for high-school students: Homepage, VK group

  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 . Donations are welcome!

• 

  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 > 10M 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

• Grad School Application:
  • How to Apply to Graduate School in the United States (by Andrew Ng).
  • Applying to Ph.D. Programs in Computer Science (by Mor Harchol-Balter)
• Job Search:
  • Tips on the Interview Process (by Jeanette Wing, CMU/Microsoft Research)
  • Success in the Job Search, see also “How to Get a Faculty Job” (Part 1a, Part 1b, Part 2 and Part 3) (by Matt Welsh, Harvard/Google)
  • Career Planning in a Research Lab (by Laura Haas, IBM Research)
  • Getting a Job in an Industrial Lab (by Mary Fernandez, AT&T Labs – Research/MentorNet)
  • Reflections on My Tenure-Track Assistant Professor Job Search (by Philip Guo, University of Rochester)
  • Getting a Research Internship (an entry on my blog)
  • Slides from CRA Career Mentoring Workshops (see e.g. slides by Jeanette Wing from 2012)
• Funding:
  • NSF Update Subscription
  • Slides from DARPA Proposer's Day 2015
  • Advice on Writing a Research Grant Proposal (by Sanjeev Arora)
  • CAREER Proposal Examples + Comments (by Adam Klivans, James Lee, Moses Charikar, Piotr Indyk , Salil Vadhan and Sariel Har-Peled)
• Wisdom and Career Advice:
  • You and Your Research (by Richard Hamming)
  • Advice to a Beginning Graduate Student (by Manuel Blum)
  • Essays and Opinions (by Oded Goldreich)
  • Career Advice and On Writing (by Terry Tao)
  • Principles of Effective Research (by Michael Nielsen)
  • Lecture on Getting Rich (by Writing a Book) (by Jeff Ullman)
  • Advice for Graduate Students and Academics (by Matt Might, see relevant topics, e.g. “Graduate School”, “Productivity”, “Writing”, “Giving Presentations”, etc).
  • What Qualities Characterize a Great PhD Student? (on Quora, see David Karger's answer).
  • A Few Words on Research for Graduate Students (by Fan Chung Graham)
  • A Survival Guide to a Ph.D (by Andrej Karpathy)
• Problem Solving: Solving Mathematical Problems (by Terry Tao).
• Problem Archives (if research problems are not enough): IMO, IOI, ACM-ICPC Live Archive, TopCoder, Kaggle.
• Online Seminars on Theoretical Computer Science: TCS+.
• Workshops: Dagstuhl, BIRS, Bertinoro, Simons Center, ICERM, IPAM, MSRI, Shonan Center, Barbados, Fields Institute, Cargese, Oberwolfach, New York Area Theory Day.
• Social: TCS community on Google+.
• Blogs: TCS Blog Aggregator, List of Math Blogs.
• Q&A: CSTheory, MathOverflow. See also top questions on CSTheory and MathOverflow, including “What Papers Should Everyone Read”, “What Books Should Everyone Read”, “What Lecture Notes Should Everyone Read”, “Advice on Good Research Practices”, “Core Algorithms Deployed”, “Algorithms from the Book”, “Examples of Common False Beliefs in Mathematics”, “Refereeing a Paper”, etc.
• Richard Feynman: “Surely You're Joking, Mr. Feynman!” and “What Do You Care What Other People Think?” (both by Ralph Leighton). IMHO, you should better read this when you are a teenager and not take it too seriously, but it's so much fun! ;)
• Comics and Other Fun Stuff (I don't read these, but I know many of my friends like them): XKCD, Abstruse Goose, Ph.D. Comics, Research in Progress.

Diversity Statement