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

Automata Theory
Stanford University via edX
Intro to Theoretical Computer Science
Udacity
Computing: Art, Magic, Science
ETH Zurich via edX
理论计算机科学基础 | Introduction to Theoretical Computer Science
Peking University via edX
Quantitative Formal Modeling and Worst-Case Performance Analysis
EIT Digital via Coursera