Tradeoffs Between Fundamental Complexity Measures of Propositional Proofs

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=TybuTwIFJNo


Duration: 1:11:48
56 views
0

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.



Other Videos By Microsoft Research


2016-08-16Advancing Environmental Understanding: the Role of eScience
2016-08-16PCPs and Expander Graphs
2016-08-16Learning and stochastic optimization with non-i.i.d. data
2016-08-16Do Not Track: Technology, Policy, and Politics
2016-08-16WiFi, Whitespace, Wireless microphones: Can They Coexist?
2016-08-16Closing the gap between weakly and fully supervised methods
2016-08-16Cloud Computing: Real-World Experiences
2016-08-16Communities, Relationships and Industries: Creating Contexts Through Social Media
2016-08-16Group Reporting and Summary
2016-08-16Making the case for ethnography as a critical dimension in media and technology studies
2016-08-16Tradeoffs Between Fundamental Complexity Measures of Propositional Proofs
2016-08-16Knowledge Ecosystems: Data-Intensive Science is More Than Speeds and Feeds
2016-08-16PARIS: Probabilistic Alignment of Relations, Instances, and Schema
2016-08-16CMA-ES ΓÇô a Stochastic Second-Order Method for Function-Value FreeNumerical Optimization
2016-08-16A new approach to temporal property verification
2016-08-16Why Nothing Matters: The Impact of Zeroing
2016-08-16Software Language Design and Engineering: Mobl & Spoofax
2016-08-16Software: Design and Performance
2016-08-16Analysing biological information processing with mechanistic modular models
2016-08-16Large-scale Retrieval with Ivory and MapReduce
2016-08-16Presentation of Jim Gray Award


Tags:
microsoft research