Tradeoffs Between Fundamental Complexity Measures of Propositional Proofs

  • Eli Ben-Sasson | Technion

What kind of theorems are easy to state yet hard to prove?

This question motivates the study of propositional proof complexity. In this introductory talk I will describe the three fundamental proof-complexity measures of proof length, width, and space. These measures correspond to different aspects of the “hardness” of proving a given theorem. Then I will discuss the surprising relationships between these three measures and conclude with accessible and intriguing open questions in this area.

Based on joint work with Jakob Nordstrom.

Speaker Details

Eli Ben-Sasson is an associate professor of computer science at Technion, Israel. His research is within theoretical computer science with recent focus on the generation and verification of automated proofs, the analysis of locally testable error correcting codes and the study of randomness arising from algebraically simple sources.

Watch Next