Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
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.