Resilience of 3-Majority Dynamics to Non-Uniform Schedulers
summary
Defines a p-epsilon scheduler that lets an adversary pick, each round, a distribution over triplets within Lp distance ε of uniform and shows precise thresholds where 3‑majority either succeeds or fails. For L∞ one can set normalized ε′=1 to disconnect S nodes (they show S up to n/5) and break consensus; but for ε′≤3/4 the protocol still reaches approximate majority in Θ(n log n) rounds with high probability provided the initial gap is increased by an ε′-dependent factor. For L1 they build an explicit scheduler (with two persistent minority agents chosen with probability ε) that forces failure unless the initial gap is Ω(ε n), so small L1 distortion already demands a linear gap.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:22OUTLINE
- 0:46DISCRETE CHEMICAL REACTION NETWORKS (CRNs)
- 2:11COMPUTATIONAL MODEL - CONT.
- 3:03EXAMPLE: COMPUTING "OR"
- 4:04BRIEF HISTORY
- 6:30WORST-CASE SCHEDULERS
- 7:45UNIFORM SCHEDULERS
- 9:233-MAJORITY DYNAMICS
- 11:54WHY APPROXIMATE MAJORITY?
- 19:24INTERMEDIATE REGIME
- 21:47WHAT CAN GO WRONG?
- 23:45THE COST OF DISCONNECTION
- 26:55RESULTS (GENERAL)
- 32:24PHASE I GONE WRONG (1)
- 37:18SUMMARY
related talks
34mNew Tools for Peak Memory Scheduling
20m(Almost) Perfect Discrete Iterative Load Balancing
26mLower Bounds on the Running Time for Scheduling and Packing Problems
01h 01mComplexity and Algorithmic Game Theory I
01h 10mOn Algorithmic Game Theory II
33mManaging High-Bandwidth Memory is a Parallel Scheduling Problem
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
58mLower Bound Issues in Computational Social Choice