Epic Fail: Emulators can tolerate some edge faults for free
summary
Proves that emulators can tolerate many edge failures without growing size: constructs f-edge-fault-tolerant 5-emulators that remain on n^{4/3} edges using a greedy spanner-like algorithm that adds an input edge only if some failure scenario still requires it, and analyzes correctness with the blocking set method. Main quantitative claim: fault tolerance is free for f up to n^{2/9} (no extra asymptotic factor), shows impossibility beyond n^{1/3}, builds emulators as subgraphs, and extends results for odd stretch 2k−1 (even k behaves differently).
AI-written summary · about
chapters (8)
- 0:00Start
- 3:25Applications of Emulators
- 7:56Emulators with Failures
- 13:16Fault Tolerant 5-emulators
- 16:31A Few Proof Ideas
- 22:57Fault Tolerant (2k - 1)-Emulators
- 25:17Open Questions
- 26:58Wrapup
related talks
01h 20mExtending Moore’s Law with Low-Cost Memory Reliability
28mHow to Build a NES Emulator
01h 01mExact Algorithms from FPT Algorithms
37mOn testing networks that compute ...
27mConsistency and Coherence of the NVIDIA Grace-Hopper Superchip
01h 02mFine-Grained Counting Complexity I
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
34mTesting Intersectingness of Uniform Families or how Dana and I intersected