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. We will focus on topics such as sublinear algorithms, randomized numerical linear algebra, streaming and sketching, and learning and testing.

What | Workshop on Algorithms for Large Data |
---|---|

When | Monday, August 23 - Wednesday, August 25, 2021 |

Where | The workshop will be held virtually. |

### Organizers

Organizers- Ainesh Bakshi (Carnegie Mellon)
- Rajesh Jayaram (Google Research NYC)
- Samson Zhou (Carnegie Mellon)

### Registration

RegistrationThe workshop is now over. Thanks for your interest in attending WALDO21!

### Speakers

Speakers- Sepehr Assadi (Rutgers)
- Clément Canonne (Sydney)
- Petros Drineas (Purdue)
- Talya Eden (MIT)
- Alina Ene (Boston University)
- Sumegha Garg (Harvard)
- Anna C. Gilbert (Yale)
- Robert Krauthgamer (Weizmann)
- Rasmus Kyng (ETH)
- Jerry Li (MSR)
- Sepideh Mahabadi (TTIC)
- Cameron Musco (UMass Amherst)
- Christopher Musco (NYU)
- Jelani Nelson (Berkeley)
- Richard Peng (Georgia Tech)
- Eric Price (UT Austin)
- Sofya Raskhodnikova (Boston University)
- Dana Ron (Tel Aviv)
- Madhu Sudan (Harvard)
- Santosh Vempala (Georgia Tech)
- Erik Waingarten (Stanford)
- David Wajc (Stanford)
- David P. Woodruff (Carnegie Mellon)
- Qin Zhang (Indiana)

### Schedule

Schedule
12:00 pm ET

Opening Remarks

12:05 pm ET

Robert Krauthgamer: Streaming Algorithms for Geometric Steiner Forest
[Abstract]

12:30 pm ET

Sepehr Assadi: Multi-Pass Graph Streaming Lower Bounds for Parameter Estimation and Property Testing Problems
[Abstract]

12:55 pm ET

Coffee Break (15 mins)

13:10 pm ET

Jelani Nelson: Optimal Bounds for Approximate Counting
[Abstract]

13:35 pm ET

Sumegha Garg: The Coin Problem with Applications to Data Streams
[Abstract]

14:00 pm ET

Junior-Senior Lunch (50 mins)

15:00 pm ET

Madhu Sudan: Streaming Complexity of Constraint Satisfaction Problems
[Abstract]

15:50 pm ET

Coffee Break (15 mins)

16:05 pm ET

Eric Price: Simulating Random Walks in Random Streams
[Abstract]

16:30 pm ET

David Wajc: Streaming Submodular Matching Meets the Primal-Dual Method
[Abstract]

12:00 pm ET

Opening Remarks

12:05 pm ET

Rasmus Kyng: Hardness Results for Structured Linear Equations and Programs
[Abstract]

12:30 pm ET

Sofya Raskhodnikova: Isoperimetric Inequalities for the Hypercube with Applications to Monotonicity Testing
[Abstract]

12:55 pm ET

Coffee Break (15 mins)

13:10 pm ET

Anna C. Gilbert: Private Inverse Problems and Source Localization
[Abstract]

13:35 pm ET

Richard Peng: Fully Dynamic Effective Resistance
[Abstract]

14:00 pm ET

Poster Session (50 mins)

15:00 pm ET

Santosh Vempala: Robustly Learning Mixtures of Arbitrary Gaussians in Polynomial Time
[Abstract]

15:25 pm ET

David P. Woodruff: Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
[Abstract]

15:50 pm ET

Coffee Break (15 mins)

16:05 pm ET

Petros Drineas: Randomized Linear Algebra for Interior Point Methods
[Abstract]

16:30 pm ET

Clément Canonne: The Price of Tolerance in Distribution Testing
[Abstract]

12:00 pm ET

Opening Remarks

12:05 pm ET

12:30 pm ET

Cameron Musco: Hutch++: Optimal Stochastic Trace Estimation
[Abstract]

12:55 pm ET

Coffee Break (15 mins)

13:10 pm ET

Talya Eden: Approximating the Arboricity in Sublinear Time
[Abstract]

14:00 pm ET

Open Problem Session (50 mins)

15:00 pm ET

Sepideh Mahabadi: Two-sided Kirszbraun Theorem
[Abstract]

15:25 pm ET

Christopher Musco: Linear and Sublinear Time Spectral Density Estimation
[Abstract]

15:50 pm ET

Coffee Break (15 mins)

16:30 pm ET

Erik Waingarten: Sketching Geometric MST and EMD
[Abstract]

### Posters

PostersTuesday, August 24th, 2-2:30 pm ET:

- Mitali Bafna (Harvard): Optimal Fine-grained Hardness of Approximation of Linear Equations
- Sabyasachi Basu (UC Santa Cruz): The Complexity of Testing All Properties of Planar Graphs, and the Role of Isomorphism
- Alex Block (Purdue): Private and Resource-Bounded Locally Decodable Codes for Insertions and Deletions
- Justin Chen (MIT): Worst-Case Analysis for Randomly Collected Data
- Tyler Chen (Washington): Simple Algorithms for Spectral Sum and Spectrum Approximation
- Zhili Feng (Carnegie Mellon): Dimensionality Reduction for the Sum-of-Distances Metric
- Mehrdad Ghadiri (Georgia Tech): Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling
- Praneeth Kacham (Carnegie Mellon): Reduced Rank Regression with Operator Norm Error
- Iden Kalemaj (Boston University): Sublinear-Time Computation in the Presence of an Online Adversary
- John Kallaugher (UT Austin): Separations and Equivalences between Turnstile Streaming and Linear Sketching
- Young-San Lin (Purdue): Online Directed Spanners and Steiner Forests
- Arvind Mahankali (Carnegie Mellon): Streaming and Distributed Algorithms for Robust Column Subset Selection
- Raphael Meyer (NYU): Hutch++: Optimal Stochastic Trace Estimation
- Tamalika Mukherjee (Purdue): Differentially Private Sublinear-Time Clustering
- Shyam Narayanan (MIT): Learning-Based Support Estimation in Sublinear Time

Tuesday, August 24th, 2:30-3 pm ET:

- Aditya and Advait Parulekar (UT Austin): L1 Regression with Lewis Weights Subsampling
- Edward (Ted) Pyne (Harvard): Local Access to Random Walks
- Archan Ray (UMass Amherst): Estimating Eigenvalues of Symmetric Indefinite Matrices
- Raghuvansh Saxena (Princeton): Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs
- Ayush Sekhari (Cornell): SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs
- Supratim Shit (Technion): Nonparametric Coreset for Clustering
- Sandeep Silwal (MIT): Adversarial Robustness of Streaming Algorithms through Importance Sampling
- Kevin Tian (Stanford): Recent Advances in List-Decodable Mean Estimation
- Arsen Vasilyan (MIT): On Learning Monotone Probability Distributions over the Boolean Cube
- Santhoshini Velusamy (Harvard): How Well Can We Approximate CSPs in Streaming Settings?
- Chen Wang (Rutgers): Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits
- Pruthuvi Maheshakya Wijewardena (Utah): Additive Error Guarantees for Weighted Low Rank Approximation
- Taisuke Yasuda (Carnegie Mellon): Exponentially Improved Dimension Reduction in L1
- Fred Zhang (Berkeley): Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
- Lichen Zhang (Carnegie Mellon): Fast Sketching of Polynomial Kernels of Polynomial Degree

### Support

SupportWALD(O)'21 is generously supported by the LEarning and Algorithms for People and Systems group and the National Science Foundation. Web design by Pedro Paredes.