Completed
Trivial Random Sampling is Optimal for Max-CUT!
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Optimal Streaming Approximations for All Boolean Max 2-CSPs and Max k-SAT
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Motivation and Spoiler
- 3 Constraint Satisfaction Problem (CSP)
- 4 CSP in the Streaming Model
- 5 Trivial Random Sampling is Optimal for Max-CUT!
- 6 Max-DICUT in the Streaming Model
- 7 Warm-up: 2/5-Approximation by [GW17]
- 8 New Idea: Random Sampling with Bias
- 9 New Relation Between Total Bias and Cut Value
- 10 Streaming Lower Bounds via Communication Complexity
- 11 Distributional Boolean Hidden Partition (DBHP) Problem contains exactly
- 12 Example of DBHP (with Parallel Repetition)
- 13 Reducing DBHP to Max-DICUT (Max-2AND)
- 14 Conclusion
- 15 Future Directions
