Sublinear Graph Simplification

Program

Sublinear Algorithms

Location

Calvin Lab auditorium

Date

Monday, July 29 – Friday, Aug. 2, 2024

Back to calendar

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:15 a.m.

Maximum Matching in $O(\log \log n)$ Passes in Dynamic Streams

Janani Sundaresan (University of Waterloo)

10:15 – 10:45 a.m.

Improved streaming algorithms for Max-DICUT via local snapshots

Santhoshini Velusamy (Toyota Technological Institute at Chicago)

10:45 – 11 a.m.

Discussions

11 – 11:30 a.m.

Break

11:30 a.m. – 12 p.m.

Online Algorithms for Spectral Hypergraph Sparsification

Yuichi Yoshida (National Institute of Informatics)

12 – 2 p.m.

Lunch (on your own)

2 – 2:45 p.m.

Almost-Optimal Sublinear Additive Spanners

Zihan Tan (Rutgers University)

2:45 – 3:15 p.m.

New algorithms for directed spanner problems and generalizations

Elena Grigorescu (Purdue)

3:15 – 3:30 p.m.

Discussions

3:30 – 4:30 p.m.

Reception

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Dynamic Matching and (Ordered) Ruzsa-Szemerédi Graphs: Towards Constructive Matching Sparsifiers

Soheil Behnezhad (Northeastern University),
Alma Ghafari (Northeastern University)

10:30 – 10:45 a.m.

Discussions

10:45 – 11:15 a.m.

Break

11:15 – 11:45 a.m.

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs

Sepehr Assadi (University of Waterloo)

11:45 a.m. – 12 p.m.

Discussions

12 – 2 p.m.

Lunch (on your own)

2 – 2:45 p.m.

Sublinear algorithms for correlation clustering

Slobodan Mitrovic (UC Davis)

2:45 – 3:15 p.m.

Fast Streaming Euclidean Clustering with Constant Space

Samson Zhou (Texas A&M University)

3:15 – 3:30 p.m.

Discussions

3:30 – 4 p.m.

Break

4 – 4:30 p.m.

Stochastic Minimum Vertex Cover with Few Queries: a 3/2-approximation

Mahsa Derakhshan (Northeastern University)

4:30 – 5 p.m.

On (1 + ε)-Approximate (Vertex) Cut Sparsifiers

Yu Chen (EPFL)

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:15 a.m.

Sparsification: Graphs, CSPs and Codes

Madhu Sudan (Harvard University)

10:15 – 10:45 a.m.

Cut Sparsification and Succinct Representation of Submodular Hypergraphs

Robert Krauthgamer (Weizmann Institute of Science)

10:45 – 11 a.m.

Discussions

11 – 11:30 a.m.

Break

11:30 a.m. – 12 p.m.

Linear Sketching Hypergraph Sparsifiers

Aaron Putterman (Harvard University)

12 – 2 p.m.

Lunch (on your own)

2 – 2:45 p.m.

Small Space Differentially Private Graph Algorithms in the Continual Release Model

Quanquan Liu (Simons Institute)

2:45 – 3:15 p.m.

Approximating Maximum Matching Requires Almost Quadratic Time

Mohammad Roghani (Stanford)

3:15 – 3:30 p.m.

Discussions

3:30 – 4 p.m.

Break

4 – 4:30 p.m.

Planar partition oracles (for bounded degree graphs) in poly(1/\eps) time

Akash Kumar (IIT Bombay)

4:30 – 5 p.m.

The approximate structure of triangle-free graphs

Yuval Wigderson (ETH Zurich)

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10 a.m.

Sparsification for communication-efficient distributed symmetry-breaking

Yannic Maus (TU Graz)

10 – 10:30 a.m.

Parallel Algorithms for Local Problems in Sparse Graphs

Jara Uitto (Aalto University)

10:30 a.m. – 10:45 p.m.

Discussions

10:45 – 11:15 a.m.

Break

11:15 – 11:45 a.m.

Maximal Matching in Bounded-deletion Streams

Christian Konrad (University of Bristol, UK)

11:45 a.m. – 12 p.m.

Discussions

12 – 2 p.m.

Lunch (on your own)

2 – 2:45 p.m.

A Quasi-Monte Carlo Algorithm for Smooth Kernel Evaluation

Erik Waingarten (University of Pennsylvania)

2:45 – 3:15 p.m.

Recent Progress on Euclidean Spanners

Hung Le (University of Massachusetts Amherst)

3:15 – 3:30 p.m.

Discussions

3:30 – 4 p.m.

Break

4 – 5 p.m.

Open Problems Session

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10 a.m.

Are there graphs whose shortest path structure requires large edge weights?

Nicole Wein (University of Michigan)

10 – 10:30 a.m.

Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier

Jane Lange (Massachusetts Institute of Technology)

10:30 – 10:45 a.m.

Discussions

10:45 – 11:15 a.m.

Break

11:15 – 11:45 a.m.

Sparsifying Set Systems for Coverage Problems

Andrew McGregor (University of Massachusetts Amherst)

11:45 a.m. – 12:15 p.m.

Graph Connectivity Using Star Contraction

Sagnik Mukhopadhyay (University of Birmingham)