Completed
Lifting with Simple Gadgets Want fog hard for deterministic communication. ► Probleme usual gadgets too strong. Also hard for randomized / GT oracle.
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Cutting Planes Measures Length Length of a proof: # of lines (steps) Can always do length O(2 ) Sometimes need length exp(n.)
- 3 Weights in Cutting Planes Weight 2 enough, but length might blow-up.
- 4 Large Weights are Needed in Cutting Planes Space Length of a proof: # of lines (steps) Space of a proof: # of lines in memory Weight of a proof: largest weight
- 5 Cutting Planes to Communication Evaluate LTF with distributed variables.
- 6 Lifting with Simple Gadgets Want fog hard for deterministic communication. ► Probleme usual gadgets too strong. Also hard for randomized / GT oracle.
- 7 More Applications: Circuits Circuits vs Formulas Monotone circuit: 0/1 values on wires; AND, OR gates. Monotone formula: tree-like monotone circuit. Theorem exp((n/polylogre)) separation between mono…
