Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
University of Chicago Title: Complexity of Algebraic and Semi-Algebraic Proofs Abstract: Algebraic and semi-algebraic proof systems make a very important part of the modern proof complexity. They explore the possibility of proving meaningful statements expressed as propositional tautologies using algebra and geometry in addition to logic. More specifically, based on the powerful Nullstellensatz/Positivestellensatz theorems, these systems manipulate with polynomial equations or inequalities rather than with logical formulas. This area is extremely well connected to other branches of theory of computing and mathematics, notably to approximation algorithms in combinatorial optimization, and it is growing fast.The talk will consist of two parts. First, we will give a general overview of the area and explain some of the connections mentioned above. In the second, more technical, part we will talk about a very recent paper on the width of semi-algebraic proofs in dynamical proof systems. Date: Thursday, January 21, 2016 Time: 3:30 pm Location: Wean Hall 8220 |