Karchmer-Wigderson Games for Hazard-free Computation
summary
Defines a hazard-free Karchmer-Wigderson game and proves its communication cost exactly matches hazard-free formula depth and its protocol size matches formula size. Shows the hazard-derivative method can only yield ~n·2^n lower bounds, so it cannot reach optimality for multiplexer. Gives a reduction from subcube intersection to the game, proves the communication matrix has rank 3^n via Kronecker products, and concludes the n-bit multiplexer needs size at least 2·3^n − 1, matching the known upper bound.
AI-written summary · about
chapters (5)
related talks
23mHow to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)
19mAlgorithms and Lower Bounds for Comparator Circuits from Shrinkage
01h 01mTop-Down Lower Bounds for Depth-Four Circuits
53mA Commentary on the Collision of Worlds
32mReed-Muller and Other Subcodes of the Sierpinski Matrix
01h 31mTutorial 1: The GCT Chasm I
47mHardness Amplification and the Approximate Degree of Constant-Depth Circuits
53mNew Lower Bounds and Derandomization for ACC, and a...