Local Reductions

on YouTube ↗43m

" summary

Proves a concrete reduction from a time-t computation to 3SAT formulas of quasi-linear size whose clause for index i is computable by a function depending on only O(1) bits of i (constant locality), and gives a projection-version with locality one (projection) for key cases. Construction uses sort-and-check simulation, sorting/routing networks, and a spreading-uniformity trick to make log-space uniform checks local. Result yields tighter Williams-style links: specific numeric thresholds (e.g. 3SAT in ~1.07^n implies new circuit lower bounds) and several new lower bounds that follow and do work.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 1:433-SAT is NP-complete
3. 2:36Clause-explicit reduction R
4. 4:18Applications of clause-explicitness
5. 6:23Previous results
6. 8:12Our results
7. 13:24Consequences of local reductions
8. 14:16SAT implies lower bounds, tightly IV
9. 19:04Do we simplify the proof of NEXP not in ACCO?
10. 20:08Background
11. 22:48The circuit
12. 23:35Reduction of NTIME(t) to Circuit-SAT
13. 33:13Check circuits
14. 34:07Sorting
15. 36:55Outline
16. 38:09Previous and our PCP reductions
17. 39:29Conclusion