Testing Intersectingness of Uniform Families or how Dana and I intersected

on YouTube ↗34m

" summary

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 testers whose query complexity is optimal or optimal up to log factors. Surprising gap: whereas non‑uniform testing requires exp(√n) queries (Chen et al.), the uniform case needs poly(1/ε) (and occasional log n or log k factors) under thresholds like ε ≳ k^2/n. Proofs use the Dinur–Friedgut junta lemma, simple random pair sampling, counting lemmas and an r‑round “capture” refinement that guarantees finding disjoint pairs.

AI-written summary · about

" chapters (7)

1. 0:00Introduction
2. 4:21Early collaboration
3. 9:49Intersectingness in uniform families
4. 13:14New algorithm results
5. 25:48Dana stories and tolerance
6. 30:13Tess the dog
7. 32:19Open problems and closing

" related talks

• 30mParameterized Inapproximability of Max k-Subset Intersection under ETHBingkai Lin · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 01h 01mExact Algorithms from FPT AlgorithmsDaniel Lokshtanov · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 01h 02mFine-Grained Counting Complexity IHolger Dell · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 29mColor Coding-Related TechniquesMeirav Zehavi · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 01h 02mFine-Grained Counting Complexity IIRadu-Cristian Curticapean · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 29mSubexponential Parameterized Complexity of Completion Problems: Survey of the Upper BoundsMarcin Pilipczuk · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 26mLower Bounds on the Running Time for Scheduling and Packing ProblemsKlaus Jansen · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 33mLower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related ProblemsMichał Pilipczuk · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms