BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Root finding in TC^0 and open induction - Jerbek\, E (Academy of S
 ciences of the Czech Republic)
DTSTART:20120330T090000Z
DTEND:20120330T093000Z
UID:TALK37199@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:It is known that elementary arithmetic operations are computab
 le in uniform TC^0\, and some (multiplication\, division) are even complet
 e for this complexity class. The corresponding theory of bounded arithmeti
 c\, VTC^0\, duly defines addition\, multiplication\, and ordering\, and pr
 oves that integers form a discretely ordered ring under these operations. 
 It is a natural question what other first-order properties of elementary a
 rithmetic operations are provable in VTC^0.\nIn particular\, we are intere
 sted whether VTC^0 (or a theory of similar\nstrength) can prove open induc
 tion in the basic language of arithmetic (Shepherdson's theory IOpen). Thi
 s turns out equivalent to the problem whether there are TC^0 root-finding 
 algorithms for constant-degree polynomials whose soundness is provable in 
 VTC^0. In this talk\, we will establish that such root-finding algorithms 
 exist in the real (or rather\, complex) world\, and we will discuss the pr
 ospects of their formalization in bounded arithmetic.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR