[Colloquium] Research at TTIC: Alexander Razborov, TTIC / Univ of Chicago

[Dawn Ellis]

When:     Friday, May 1st at noon

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

Who:       Alexander Razborov, TTIC/Univ of Chicago

Title:       COMPLEXITY OF PROPOSITIONAL PROOFS

Abstract:

Propositional proof complexity asks how difficult it is to
prove true facts by reasoning strictly within a specified
class of arguments called proof systems. The generic
notions of a "true fact" and a "proof system" can be
instantiated, depending on the context, by quite a number
of different things, and this partly explains the fact that
proof complexity is well connected to many other areas.

In this talk we will attempt to:

1. Explain basic concepts of propositional proof complexity
and its connections to other disciplines. Among the latter,
we will particularly emphasize connections to practical SAT
solving and combinatorial optimization;

2. Talk about my recent result providing an exceptionally
strong tradeoff between width and tree-like resolution
size.

Both parts will pay a special attention to open problems and
directions for future research.




***************************************
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


-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150424/ea3d5b2c/attachment.htm