YoVDO

Polynomial Calculus Space and Resolution Width

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Mathematical logic Courses Theoretical Computer Science Courses Space Complexity Courses

Course Description

Overview

Explore the intricacies of polynomial calculus space and resolution width in this 22-minute IEEE conference talk presented by Nicola Galesi, Leszek A. Kolodziejczyk, and Neil Thapen. Delve into proof complexity, focusing on resolution proof systems and space complexity. Examine proof techniques such as contradiction and backward induction, and discover a combinatorial characterization of total spaces with squared polynomial calculus. Investigate the consequences of these findings and consider whether the presented bounds are tight. Gain valuable insights into advanced mathematical concepts and their applications in proof theory.

Syllabus

Intro
Proof complexity
Resolution proof system
Space complexity
Proof by contradiction
Proof by backward induction
A combinatorial characterization
Total spaces with squared
Polynomial calculus
Consequences
Are these bounds tight


Taught by

IEEE FOCS: Foundations of Computer Science

Tags

Related Courses

数据结构与算法第二部分 | Data Structures and Algorithms Part 2
Peking University via edX
Computational Complexity Theory
Indian Institute of Technology Kanpur via Swayam
The Complete Data Structures and Algorithms Course in Python
Udemy
Computational Complexity
IIT Hyderabad via Swayam
Introduction to Algorithms Course (How To)
Treehouse