Explore the intricacies of lifting techniques in computational complexity theory and their applications to circuit and proof complexity. Delve into Cutting Planes measures, including length, weight, and space, and their implications for proof complexity. Examine the connection between Cutting Planes and communication complexity, focusing on the evaluation of linear threshold functions with distributed variables. Investigate the use of simple gadgets in lifting and their advantages over traditional gadgets. Discover additional applications in circuit complexity, particularly the exponential separation between monotone circuits and monotone formulas. Learn from experts in the field as they present their research findings and insights in this IEEE conference talk.
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Overview
Syllabus
Intro
Cutting Planes Measures Length Length of a proof: # of lines (steps) Can always do length O(2 ) Sometimes need length exp(n.)
Weights in Cutting Planes Weight 2 enough, but length might blow-up.
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
Cutting Planes to Communication Evaluate LTF with distributed variables.
Lifting with Simple Gadgets Want fog hard for deterministic communication. â–º Probleme usual gadgets too strong. Also hard for randomized / GT oracle.
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 monotone circuits and monotone formulas.
Taught by
IEEE FOCS: Foundations of Computer Science
