Sublinear Algorithms Boot Camp 2024
2024-05-21..2024-05-24
Berkeley, United States
as the organisers put it
This summer program brings together researchers from various areas of sublinear algorithms to explore new topics, tools, and connections between models, as well as promising future directions for the field.
who it's for
algorithms researchers, theoretical computer scientists, graduate students in algorithms, distributed systems engineers, data engineers, machine learning researchers, research software engineers
topics
graph property testing; Boolean function testing; sublinear triangle counting; sampling for sublinear algorithms; MPC graph algorithms; distributed lower bounds for MPC; sublinear graph coloring; data stream algorithms; coresets for sublinear algorithms; multi-pass streaming lower bounds; adversarially robust streaming; sketching and randomized linear algebra
| title | author | length |
|---|---|---|
| Property Testing for Graphs | Artur Czumaj | 01h 23m |
Survey of graph property testing that draws a sharp line between models and gives concrete bounds: dense graphs admit constant‑query testers for every… | ||
| Testing Boolean Functions | Erik Waingarten | 01h 02m |
Overview of concrete results and algorithms: property testing of Boolean functions centers on very low-query testers. The BLR linearity tester checks… | ||
| Counting Subgraphs in Sublinear Time | C. Seshadhri | 01h 02m |
Shows concrete sublinear estimators and their costs: sampling √n uniform vertices gives a 2-approx for average degree (Feige), while an orientation by degree… | ||
| Sampling Big Ideas in Sublinear Algorithms | Edith Cohen | 01h 04m |
Presents concrete algorithms: use order-statistics scoring (exponential or priority hashes) to get PPSWOR without knowing total weight, implementable in… | ||
| An Introduction to Distributed, Massively Parallel, and Local Computation Algorithms | Mohsen Ghaffari | 01h 20m |
Introduces three concrete models and concrete translations: synchronous message‑passing measures rounds, giving Johansson’s randomized coloring that finishes… | ||
| Graph Algorithms in the MPC Model | Slobodan Mitrovic | 01h 05m |
Describes a concrete design recipe that turns classic parallel primitives into MPC routines by combining graph sparsification plus simulation of PRAM/CONGEST… | ||
| Conditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds | Artur Czumaj | 01h 02m |
Shows that MPC with linear local space is essentially equivalent to congested clique equivalence, so unconditional lower bounds would imply circuit complexity… | ||
| Graph Coloring Through the Sublinear Lens | Sepehr Assadi | 01h 03m |
Shows that sampling O(log n) colors per vertex from the Δ+1 palette suffices so the graph is list-colorable from those lists (called palette sparsification)… | ||
| An Overview on Data Streams Algorithms | Andrew McGregor | 01h 21m |
Twenty years of graph-streaming results compress into concrete primitives and bounds: L0 sampling via linear sketches lets one pick a uniform live edge with… | ||
| Coresets and Their Applications to Design Sublinear Algorithms | Sepideh Mahabadi | 52m |
Coresets are small weighted subsets that provably approximate optimization costs: 1-center reduces to 2 points with a constant factor, k‑center uses Gonzalez… | ||
| New Advances on Multi-Pass Graph Streaming Lower Bounds | Sepehr Assadi | 01h 05m |
Proves that semi‑streaming MIS needs Theta(log log n) passes by reducing bounded‑round communication to streaming, using round‑elimination on a matrix of… | ||
| Adversarially Robust Streaming Algorithms | Omri Ben-Eliezer | 01h 03m |
Shows that classic linear sketches fail against adaptive streams and gives concrete remedies: maintain multiple black‑box copies and sketch switching based on… | ||
| Distribution Testing: Hypothesis Testing from Very Little (or Very Private) Data | Clément Canonne | 01h 17m |
Overview of concrete results: distribution testing under total-variation needs Θ(√k/ε²) samples for uniformity, and common reductions let many identity tests… | ||
| Testing Assumptions of Learning Algorithms | Arsen Vasilyan | 59m |
Introduces a framework that testable agnostic learning actually either accepts and outputs a classifier with error ≤ OPT+ε or rejects, using a concrete… | ||
| Sketching and Randomized Linear Algebra | David P. Woodruff | 01h 04m |
Shows that random sketches preserve norms and dot products via the Johnson-Lindenstrauss lemma (r = Θ(1/ε^2 log 1/δ)), extend to approximate matrix product… | ||
| Sublinear Time Algorithms for Estimating Edit Distance | Barna Saha | 01h 08m |
Distinguishes edit distance ≤k from >k^2 in sublinear time and gives concrete algorithms and limits: an adaptive route uses longest common extension queries… | ||
| nothing matches | ||