YoVDO

Semi-Algebraic Proofs, IPS Lower Bounds and the τ-Conjecture

Offered By: Association for Computing Machinery (ACM) via YouTube

Tags

Theoretical Computer Science Courses Mathematical logic Courses

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 Logic
Stanford 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