Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds
summary
Proves that noisy-CAS vs CAS can incur the worst-case slowdown Θ(log n): any adaptive protocol that uses √n rounds on CAS yields an equivalent beeping (OR) lower bound of √n·log n rounds, so adding correlated stochastic noise forces a log n overhead. Key tools are a large fooling set (size (√n)^{√n}) and the construction of many localized hybrids to amplify errors and extend deterministic fooling-set arguments to randomized beeping protocols; the separation is explicit and tight.
AI-written summary · about
chapters (9)
- 0:00Intro
- 0:24CAS channel for wireless communication
- 1:17CAS channel with noise
- 4:14Main Result
- 5:51The BEEPING channel
- 6:43The hard function
- 7:53The fooling set technique
- 11:45A large fooling set.
- 13:46Separating BEEPING from CAS.
related talks
38mSpace and Time Bounded Multiversion Garbage Collection
20m(Almost) Perfect Discrete Iterative Load Balancing
01h 10mComplexity and Algorithmic Game Theory II
01h 31mCircuits of Bounded Depth
52mNonblocking algorithms/ CAS/Atomics
10mInvestigating Stealthy Latency Attacks Against Camera-Based Object...
30mLower Bound Results for Hard Problems Related to Finite Automata
01h 20mExtending Moore’s Law with Low-Cost Memory Reliability