Semi-Algebraic Proofs, IPS Lower Bounds and the τ-Conjecture
Offered By: Association for Computing Machinery (ACM) via YouTube
Course Description
Overview
Explore the intricacies of semi-algebraic proofs, IPS lower bounds, and the τ-Conjecture in this 29-minute conference talk presented at the Association for Computing Machinery (ACM). Delve into the question "Can a Natural Number be Negative?" as the speaker guides you through key concepts such as the Binary Value Principle and Proof Complexity. Gain insights into the motivations behind semi-algebraic proofs and their applications. Learn about the definition of Algebraic Circuits and how they relate to semi-algebraic proofs. Examine illustrations that clarify complex ideas and understand the significance of IPS Upper Bounds in this context. This talk provides a comprehensive overview of advanced topics in computational complexity theory, suitable for those with a background in theoretical computer science or mathematics.
Syllabus
Introduction
Binary Value Principle
Proof Complexity
Motivation
SemiAlgebraic Proof
Motivations
Definition of Algebraic Circuit
SemiAlgebraic Proofs
Illustration
IPS Upper Bound
Conclusion
Taught by
Association for Computing Machinery (ACM)
Related Courses
Introduction to LogicStanford University via Coursera Logic: Language and Information 1
University of Melbourne via Coursera Logic: Language and Information 2
University of Melbourne via Coursera Information Service Engineering
openHPI Language, Proof and Logic
Stanford University via edX