Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Offered By: IEEE via YouTube
Course Description
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
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE 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