A Commentary on the Collision of Worlds
summary
A précis of the concrete claims: Allender’s 2001 survey promotes a variant K^T (capital T) that relates tightly to circuit complexity and to MCSP via a time‑local compression view, uses Nisan/Wigderson style PRGs to show MKTP not in AC0, and frames equivalences between circuit lower bounds and large gaps between K^T and time‑bounded K. Tools and followups: reductions, hardness‑to‑PRG paradigms, average‑case hypotheses (planted clique, k‑SAT) and characterizations of cryptography (one‑way functions ↔ KT hard on average). Several later papers instantiate and extend these specific reductions and separations.
AI-written summary · about
chapters (11)
- 0:00Welcome and logistics
- 3:04Introduction to the program
- 4:02Defining meta-complexity
- 6:10Foundational literature
- 9:20Contributions of Eric Allender
- 13:28K-capital-T complexity
- 21:59Results and lower bounds
- 31:10Complexity characterizations
- 38:25Recent developments
- 41:06The PRG paradigm
- 48:56Conclusion and closing
related talks
01h 01mThe Gospel According to TCS
01h 22mTutorial 5: The GCT Chasm II
01h 31mTutorial 1: The GCT Chasm I
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
22mNew Lower Bounds and Derandomization for ACC, and a...
19mAlgorithms and Lower Bounds for Comparator Circuits from Shrinkage
01h 00mThe Classification Program for Counting Problems I
01h 02mTheory and Control