This course teaches the KRW Composition Theorems via Lifting. The learning outcomes include understanding Boolean circuits, the KRW approach, the KRW conjecture, and the Karchmer-Wigderson Theorem. Students will learn about the state of the art, the Monotone KRW conjecture, and various composition results. The teaching method involves theoretical explanations and informal discussions. The intended audience for this course is individuals interested in theoretical computer science and mathematical logic.
Overview
Syllabus
Intro
Boolean circuits
The KRW approach
The KRW conjecture
Our results (very informal)
Karchmer-Wigderson Theorem
State of the art
Monotone KRW conjecture
Our monotone result
Semi-monotone composition
Our semi-monotone result
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
-
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
-
Agreement Testing Theorems on Layered Set Systems
-
Derandomization from Algebraic Hardness - Treading the Borders
-
More Barriers for Rank Methods, via a "Numeric to Symbolic" Transfer
-
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank
-
Hypergraph K-Cut for Fixed K in Deterministic Polynomial Time
