[Colloquium] 5/27 Research at TTIC: Alexander Razborov, TTIC

[Mary Marre]

When:     Friday, May 27th at noon

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:      Alexander Razborov, TTIC


Title:        Complexity of Semi-Algebraic and Algebraic Proofs

Abstract: Semi-algebraic and algebraic proof systems make a very important
part of the modern proof complexity. They explore the possibility of
proving meaningful statements using algebra and geometry instead of or in
addition to logic and manipulate with polynomial equations or inequalities
rather than with logical formulas. Many of these systems are based on the
powerful Nullstellensatz/Positivstellensatz theorems, while others are
underlined by more ad hoc principles. This area is extremely well connected
to other branches of computer science and mathematics, notably to
approximation algorithms in combinatorial optimization, and it is growing
fast.

The talk will consist of two parts. First, I will give a general overview
of the area and explain some of the connections mentioned above. Time
permitting, in the second, more technical, part I will give some details
about my recent paper on the width of semi-algebraic proofs in dynamical
proof systems like Cutting Planes or Lovasz-Schrijver.


************************************************************
*************************************************

*Research at TTIC Seminar Series*

TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact David McAllester at
mcallester at ttic.edu



Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757 <%28773%29%20834-1757>*
*f: (773) 357-6970 <%28773%29%20357-6970>*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160520/83d007a4/attachment.htm