Workshop on Local Algorithms (WoLA) 2024
2024-08-05..2024-08-07
Berkeley, United States
who it's for
property testing researchers, sublinear algorithms researchers, distribution testing researchers, graph algorithm researchers, streaming algorithm researchers, theoretical computer scientists, machine learning researchers
topics
edge sampling under neighbor queries; counting graph subgraphs; testing k-uniform intersecting families; property testing of ReLU networks; bounded-degree graph testing; conditional sampling for distributions; tolerant property testing and distance approximation; low-degree testing over the reals; semi-streaming maximal independent set; semi-streaming (1+epsilon)-approximate maximum matching; interactive proofs for verifiable data science; instance-optimal collision and subgraph detection
| title | author | length |
|---|---|---|
| On counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly) | Talya Eden | 41m |
Shows an algorithm that returns a nearly uniform edge under the vertex/degree/neighbor query model and then makes it exactly uniform, using pointwise closeness… | ||
| Testing Intersectingness of Uniform Families or how Dana and I intersected | Michal Parnas | 34m |
Gives efficient algorithms that test whether a k‑uniform family over [n] is intersecting or ε‑far, including a tolerant tester and one‑sided non‑adaptive… | ||
| On testing networks that compute ... | Artur Czumaj | 37m |
Introduces a property-testing model for fully connected feedforward ReLU networks where distance means changing at most an epsilon-fraction of weights per… | ||
| Recent Developments in Testing Bounded-Degree Graphs | Oded Goldreich | 46m |
Bounded-degree graphs are tested via the incident-function oracle with constant degree d; the talk gives three concrete developments: a two-graph isomorphism… | ||
| Property Testing with Incomplete or Manipulated Inputs | Sofya Raskhodnikova | 44m |
Introduces an online erasure/corruption oracle that, after each query, can erase or corrupt up to t input locations; uses Fourier analysis and affine-subspace… | ||
| Conditional Sampling for Distribution Testing | Clément Canonne | 10m |
Shows that access to conditional samples yields testers whose query complexity is poly(1/ε) testers and largely domain-size independent, giving algorithms for… | ||
| Monotonicity testing, routing, and a theorem of Lehman and Ron | C. Seshadhri | 32m |
States the Lehman–Ron routing theorem: given two same-level subsets S and T of the directed d‑cube with a bijection matching each s to a larger t, there exist… | ||
| Dana is NOT average | Ronitt Rubinfeld | 41m |
Average-case LCAs for random inputs give concrete gains: k-spanner constructions on G(n,p) achieve size/stretch tradeoffs impossible in the worst case while… | ||
| Verifiable Data Science via Interactive Proofs | Guy N. Rothblum | 01h 07m |
Work describes concrete interactive‑proof systems that let a lightweight verifier check statistical claims using far fewer samples than re‑running the… | ||
| Talk By Tal Herman | Tal Herman | 25m |
Protocol shows how to verifiably obtain a tagged sample of size roughly √N using about √N samples and √N verifier time by interacting with a prover that… | ||
| Low Degree Testing over the Reals | Esther Kelman | 33m |
Gives a distribution-free local tester that decides whether a function R^n → R has total degree ≤ d with query complexity independent of n (depends on d and ε)… | ||
| On the instance optimality of detecting collisions and subgraphs | Omri Ben-Eliezer | 26m |
Characterizes when knowing an unlabeled copy of the input helps: a trichotomy shows very simple targets are O(1) instance optimal, most targets incur a… | ||
| Distribution Learning Meets Graph Structure Sampling | Sayantan Sen | 27m |
Draws a concrete bridge from online expert algorithms to PAC learning of graphical models: running EWA or RWM on iid samples with log loss gives an… | ||
| The long path to \sqrt{d} monotonicity testers | C. Seshadhri | 56m |
Shows an almost-complete resolution: non-adaptive monotonicity testing on {n}^d uses √d query "path testers" that run short upward random walks (length ≈√d)… | ||
| Privately Evaluating Untrusted Black-Box Functions | Sofya Raskhodnikova | 01h 03m |
Two settings: automated sensitivity detection (analyst supplies only black-box f and its finite range) and the provided sensitivity bound case. The work builds… | ||
| O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set | Sepehr Assadi | 34m |
Shows an unconditional lower bound that any semi‑streaming algorithm that finds a maximal independent set with constant success probability requires Ω(log log… | ||
| Toward Optimal Semi-streaming Algorithm for (1+ε)-approximate Maximum Matching | Wen-Horng Sheu | 31m |
Deterministic algorithm achieves O(ε^-6) semi-streaming passes for (1+ε)-approximate maximum matching on general graphs, improving prior O(ε^-19). It… | ||
| Towards Practical Distribution Testing | Yash Pote | 23m |
Claims a first polynomial algorithm to estimate total variation distance under subcube conditioning, returning an ε-accurate TV estimate with constant success… | ||
| A Strong Separation for Adversarially Robust L_0 Estimation for Linear Sketches | Samson Zhou | 30m |
Gives the first adaptive attack against linear sketches for turnstile L_0 estimation, showing any sketch that achieves a constant-factor gap must use… | ||
| Let’s Try and Be More Tolerant: On Tolerant Property Testing and Distance Approximation | Dana Ron | 59m |
Gives concrete algorithms and separations: monotonicity over [1..n] is distance-approximated by estimating the size of a maximal matching in the violation… | ||
| nothing matches | ||