Polynomial Calculus Space and Resolution Width
Offered By: IEEE via YouTube
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
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube