-----------------------------------------------------------------------------
<p>
SPEAKER: Antonina Kolokolova, University of Toronto 
<p>

TITLE:   
Bounded arithmetic and descriptive complexity: two views of polynomial time.
<p>

TIME:    Tuesday, February 20, 11:30 am;  ASB 9705
<p>

ABSTRACT: This talk will focus on two connections between complexity theory and
logic, namely, bounded arithmetic and descriptive complexity. The former
is concerned with proving totality of functions, the latter with
complexity of expressing properties. By combining the two approaches we
build a second-order system of bounded arithmetic capturing polynomial
time reasoning, the hardest complexity class to represent in this
setting. Our system has a simple language and set of axioms; moreover, as
opposed to other systems capturing P, it is finitely axiomatizable. This
talk will be non-technical and will not assume any prior knowledge of
bounded arithmetic or descriptive complexity.
<p>

ABOUT THE SPEAKER: Antonina is a PhD student of Prof. Stephen Cook.
She will be talking about the results of her 
Masters thesis, also presented in a joint paper
with Stephen Cook. Her thesis and the paper are 
available on the web.  
<p>

Antonina's web page: http://www.cs.toronto.edu/~kol
Extended Abstract: http://www.cs.toronto.edu/~kol/theory/vhorn_lics.ps
Full Paper: http://www.cs.toronto.edu/~kol/theory/vhorn_lics_full.ps
-----------------------------------------------------------------------------