Completed
Step 1: mild randomness also kills structure
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Decision List Compression by Mild Random Restrictions
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Decision list (DL)
- 3 Main result
- 4 Applications
- 5 More definitions
- 6 randomness kills structure
- 7 Step 1: mild randomness also kills structure
- 8 compression - redundant rules
- 9 Step 2: compression - less useful rules
- 10 Step 2: compression - approximator
- 11 noise stability
- 12 bridging lemma
- 13 putting everything together
- 14 Upper bound compression
