Locating Linear Decision Lists within TC^0

on YouTube ↗35m

" summary

Examines where linear decision lists (LDLs) fit in the circuit complexity class TC^0, focusing on relationships between LDLs and threshold circuits. Uses established models—linear decision lists and constant-depth polynomial-size threshold circuits—to identify inclusions or separations within TC^0.

AI-written summary · about

" chapters (10)

1. 0:00Start
2. 7:49Some known lower bounds for parallel tests
3. 9:21Known lower bounds for sequential tests
4. 14:14Proof Step 1 (cont'd)
5. 17:02Proof Step 2 (cont'd)
6. 17:34Harper's Theorem
7. 20:22Spectral classes
8. 22:55Why we got interested in Decision Lists...
9. 25:14Transferring LDL lower bounds to QCP
10. 33:12Summary