YoVDO

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Circuit Complexity Courses

Course Description

Overview

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.

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

Tags

Related Courses

An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature
IEEE via YouTube
Computation in the Brain Tutorial - Part 2
IEEE via YouTube
Computation in the Brain - Part 1
IEEE via YouTube
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube
Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube