Extroverted Sublinear Algorithms

Program

Sublinear Algorithms

Location

Calvin Lab Auditorium

Date

Monday, June 17 – Friday, June 21, 2024

Back to calendar

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10 a.m.

New upper and lower bounds on approximate counting

Jelani Nelson (Simons Institute)

10 – 10:30 a.m.

Locally Private Histograms in All Privacy Regimes

Clément Canonne (University of Sydney)

10:30 – 10:45 a.m.

Discussion

10:45 – 11:15 a.m.

Break

11:15 – 11:45 a.m.

Shaving logs by weighing coins

Deeparnab Chakrabarty (Dartmouth College)

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

Optimal Quantile Estimation for Streams

Mihir Singhal (UC Berkeley)

12:15 – 12:30 p.m.

Discussion

12:30 – 2 p.m.

Lunch (on your own)

2 – 2:30 p.m.

O(log s)-Approximate Nearest Neighbor Search for the Earth Mover’s Distance

Rajesh Jayaram (Google Research NYC)

2:30 – 3 p.m.

Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree

Peilin Zhong (Google)

3 – 3:30 p.m.

Efficiently Computing Similarities to Private Datasets

Sandeep Silwal (MIT)

3:30 – 3:45 p.m.

Discussion

3:45 – 4:45 p.m.

Reception

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10 a.m.

ML Efficiency for Large Models: From Data Efficiency to Faster Transformers

Vahab Mirrokni (Google Research, NYC)

10 – 10:30 a.m.

Sub-Linear Algorithms meets Large Language Models

Anshumali Shrivastava (Rice University)

10:30 – 10:45 a.m.

Discussion

10:45 – 11:15 a.m.

Break

11:15 – 11:45 a.m.

Randomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomposition

Tamara Kolda (MathSci.ai)

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

Long-context Attention in Near-Linear Time

David Woodruff (Carnegie Mellon University)

12:15 – 12:30 p.m.

Discussion

12:30 – 2 p.m.

Lunch (on your own)

2 – 2:30 p.m.

Sublinear-Time Algorithms in Learning

Ronitt Rubinfeld (Massachusetts Institute of Technology)

2:30 – 3:10 p.m.

Differential Privacy under Continual Observation

Sofya Raskhodnikova (Boston University)

3:10 – 3:40 p.m.

Large Scale Private Learning on Data Streams, and the BLTs

Abhradeep Guha Thakurta (Google DeepMind)

3:40 – 3:45 p.m.

Discussion

3:45 – 4 p.m.

Break

4 – 5 p.m.

Panel on Sub-linear Algorithms Meet Practice (Not Recorded)

TBD ()

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10 a.m.

Sublinear Insights: A Faster (Classical) Algorithm for Edge Coloring

Sepehr Assadi (University of Waterloo and Rutgers University)

10 – 10:30 a.m.

Linear and sublinear algorithms for graphlet sampling

Marco Bressan (University of Milan)

10:30 – 10:45 a.m.

Discussion

10:45 – 11:15 a.m.

Break

11:15 – 11:45 a.m.

Sublinear algorithms in social networks via core-periphery decomposition

Omri Ben-Eliezer (Simons Institute)

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

Sublinear time algorithms for better than 1/2 approximation algorithms for max-cut on expanders

Akash Kumar (IIT Bombay)

12:15 – 12:30 p.m.

Discussion

12:30 – 2 p.m.

Lunch (on your own)

2 – 2:30 p.m.

Streaming Algorithms for Connectivity Augmentation

Ali Vakilian (Toyota Technological Institute at Chicago)

2:30 – 3 p.m.

Sublinear Algorithms in Adversarial Environment

Ilya Mironov (Google Brain)

3 – 3:30 p.m.

Applications of Sub-linear Algorithms on Other Fields

Vladimir Braverman (Rice University)

3:30 – 3:45 p.m.

Discussion

3:45 – 4 p.m.

Break

4 – 5 p.m.

Open Problem Session

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10 a.m.

Hypothesis selection with computational constraints

Maryam Aliakbarpour (Rice University)

10 – 10:30 a.m.

A Bi-metric Framework for Fast Similarity Search

Piotr Indyk (Massachusetts Institute of Technology)

10:30 – 10:45 a.m.

Discussion

10:45 – 11:15 a.m.

Break

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

Lightning Talks

12:30 – 2 p.m.

Lunch (on your own) and Close