Workshop on Algorithms for Large Data (Online) 2025

This workshop aims to foster collaborations between researchers across multiple disciplines through a set of central questions and techniques for algorithm design for large data. By bringing together experts from diverse fields, we seek to explore innovative approaches and shared challenges in this rapidly evolving area. Due to a generous grant from SIGACT, the workshop is free to attend for all interested participants.

What Workshop on Algorithms for Large Data (Online)
When Monday, April 14 - Wednesday, April 16, 2025
Where The workshop will be held virtually.

Organizers

Organizers

Registration

Registration

The workshop is now over. Thanks for your interest in WALDO 2025!

Speakers

Speakers  

Schedule

          Schedule
See below for talk details, including abstracts.
Time (pm ET) Day 1 (Mon Apr 14) Day 2 (Tue Apr 15) Day 3 (Wed Apr 16)
12:00-12:05 ACM Remarks Steering Committee Organizers
12:05-12:30 Anupam Gupta Michael Kapralov Ronitt Rubinfeld
12:30-12:55 Mark Braverman Sanjeev Khanna Sofya Raskhodnikova
12:55-13:10 Coffee Break Coffee Break Coffee Break
13:10-13:35 David Woodruff Nicole Wein Piotr Indyk
13:35-14:00 Slobodan Mitrović Karthik C.S. Sumegha Garg
14:00-14:25 Poster Session Soheil Behnezhad Poster Session
14:25-15:00 Poster Session Lunch Poster Session
15:00-15:25 Madhur Tulsiani Vincent Cohen-Addad Sepehr Assadi
15:25-15:50 Meghal Gupta Elena Grigorescu Huacheng Yu
15:50-16:05 Coffee Break Coffee Break Coffee Break
16:05-16:30 Rocco Servedio Jane Lange Maryam Aliakbarpour
16:30-16:55 Pravesh Kothari Joshua Brakensiek Clément Canonne
         
12:00 pm ET
Opening Remarks by SIGACT

12:05pm ET
Anupam Gupta: The Price of Explainability for Clustering [Abstract]

12:30 pm ET
Mark Braverman: Optimality of Frequency Moment Estimation [Abstract]

12:55 pm ET
Coffee Break (15 mins)

13:10 pm ET
David P. Woodruff: Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness  [Abstract]

13:35 pm ET
Slobodan Mitrović: Computing Graph Cuts Privately [Abstract]

14:00 pm ET
Monday Poster Session

15:00 pm ET
Madhur Tulsiani: Expander Graphs and Optimally List-Decodable Codes [Abstract]

15:25 pm ET
Meghal Gupta: Stream-Decodable Error-Correcting Codes [Abstract]

15:50 pm ET
Coffee Break (15 mins)

16:05 pm ET
Rocco Servedio: Is Nasty Noise Actually Harder than Malicious Noise? [Abstract]

16:30 pm ET
Pravesh Kothari: The Quasi-polynomial Low-Degree Conjecture is False [Abstract]

12:00 pm ET
Opening Remarks by Steering Committee

12:05 pm ET
Michael Kapralov: Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions [Abstract]

12:30 pm ET
Sanjeev Khanna: Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms [Abstract]

12:55 pm ET
Coffee Break (15 mins)

13:10 pm ET
Nicole Wein: Covering Approximate Shortest Paths with DAGs [Abstract]

13:35 pm ET
Karthik C.S.: Near-Optimal Lower Bound for Parameterized Euclidean k-means [Abstract]

14:00 pm ET
Soheil Behnezhad: Vizing's Theorem in Near-Linear Time [Abstract]

14:25 pm ET
Break (35 mins)

15:00 pm ET
Vincent Cohen-Addad: Solving the Correlation Cluster LP in Sublinear Time [Abstract]

15:25 pm ET
Elena Grigorescu: Differential Privacy and Sublinear-Time are Incompatible Sometimes [Abstract]

15:50 pm ET
Coffee Break (15 mins)

16:05 pm ET
Jane Lange: Lifting Uniform Learners via Distributional Decomposition [Abstract]

16:30 pm ET
Josh Brakensiek: Redundancy Is All You Need (for Sparsification) [Abstract]

12:00 pm ET
Opening Remarks by Organizers

12:05 pm ET
Ronitt Rubinfeld: Efficient 2-Coloring of Random Uniform Hypergraphs [Abstract]

12:30 pm ET
Sofya Raskhodnikova: Fully Dynamic Algorithms for Graphs with Edge Differential Privacy [Abstract]

12:55 pm ET
Coffee Break (15 mins)

13:10 pm ET
Piotr Indyk: A Bi-metric Framework for Fast Similarity Search [Abstract]

13:35 pm ET
Sumegha Garg: A New Information Complexity Measure for Multi-Pass Streaming Algorithms [Abstract]

14:00 pm ET
Wednesday Poster Session

15:00 pm ET
Sepehr Assadi: Distributed Triangle Detection is Hard in Few Rounds [Abstract]

15:25 pm ET
Huacheng Yu: Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors [Abstract]

15:50 pm ET
Coffee Break (15 mins)

16:05 pm ET
Maryam Aliakbarpour: Leveraging Predictions for Efficient Hypothesis Testing in Discrete Distributions [Abstract]

16:30 pm ET
Clément Canonne: Better Private Distribution Testing by Leveraging Unverified Auxiliary Data [Abstract]

Posters

Posters
Monday Poster Session: Wednesday Poster Session:

Support

Support

WALDO 2025 is generously supported by a community grant from SIGACT. Web design by Pedro Paredes.

Steering Committee

Steering Committee