Decision List Compression by Mild Random Restrictions

Explore the concept of decision list compression through mild random restrictions in this 20-minute ACM conference talk. Delve into the main results, applications, and key definitions surrounding decision lists. Discover how randomness affects structure and learn about compression techniques for redundant and less useful rules. Examine the role of approximators, noise stability, and the bridging lemma in the compression process. Gain insights into upper bound compression and understand how all these elements come together to form a comprehensive understanding of decision list compression techniques.

Intro
Decision list (DL)
Main result
Applications
More definitions
randomness kills structure
Step 1: mild randomness also kills structure
compression - redundant rules
Step 2: compression - less useful rules
Step 2: compression - approximator
noise stability
bridging lemma
putting everything together
Upper bound compression