Super-critical Trade-offs in Resolution over Parities Via Lifting

Learn about super-critical trade-offs in resolution over parities through a lifting technique in this 29-minute conference talk by Arkadev Chattopadhyay, presented as joint work with Pavel Dvořák at the Fields Institute. Explore advanced concepts in computational complexity theory, specifically focusing on resolution proof systems and their relationship to parity constraints. Discover how lifting methods can be applied to establish trade-offs that go beyond traditional critical thresholds in proof complexity. Examine the mathematical foundations underlying these super-critical phenomena and understand their implications for understanding the power and limitations of resolution-based proof systems when dealing with parity-related constraints.