YoVDO

A Brief Tour of Proof Complexity - Lower Bounds and Open Problems - Toniann Pitassi

Offered By: Institute for Advanced Study via YouTube

Tags

Computer Science Courses Discrete Mathematics Courses Pigeonhole Principle Courses Truth-tables Courses Induction Courses

Course Description

Overview

Explore the fascinating world of proof complexity in this comprehensive computer science seminar. Delve into the definition of proof systems, polynomial bounded proof systems, and specific proof systems. Examine induction, truth tables, and the Pigeonhole Principle. Investigate lower bounds and standard proof systems, including their rules and proof completeness. Gain insights into open problems in the field as presented by Toniann Pitassi, a visiting professor from the University of Toronto. Enhance your understanding of discrete mathematics and theoretical computer science through this in-depth lecture from the Institute for Advanced Study.

Syllabus

Intro
Definition of a proof system
Polynomial bounded proof systems
Specific proof systems
Induction
Truth Tables
Pigeonhole Principle
What is the count
Lower Bounds
Standard Proof Systems
Rules
Proof completeness


Taught by

Institute for Advanced Study

Related Courses

Think Again II: How to Reason Deductively
Duke University via Coursera
Understanding Maths and Logic in Computer Science
Raspberry Pi Foundation via FutureLearn
Qualitative Comparative Analysis (QCA)
Erasmus University Rotterdam via Coursera
Critical Thinking
Shiv Nadar University via Swayam
Introduction to Logic (Geometry Unit 2)
Udemy