BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Root finding in TC^0 and open induction - Jerbek\,
E (Academy of Sciences of the Czech Republic)
DTSTART;TZID=Europe/London:20120330T100000
DTEND;TZID=Europe/London:20120330T103000
UID:TALK37199AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/37199
DESCRIPTION:It is known that elementary arithmetic operations
are computable in uniform TC^0\, and some (multipl
ication\, division) are even complete for this com
plexity class. The corresponding theory of bounded
arithmetic\, VTC^0\, duly defines addition\, mult
iplication\, and ordering\, and proves that intege
rs form a discretely ordered ring under these oper
ations. It is a natural question what other first-
order properties of elementary arithmetic operatio
ns are provable in VTC^0.\nIn particular\, we are
interested whether VTC^0 (or a theory of similar\n
strength) can prove open induction in the basic la
nguage of arithmetic (Shepherdson's theory IOpen).
This turns out equivalent to the problem whether
there are TC^0 root-finding algorithms for constan
t-degree polynomials whose soundness is provable i
n VTC^0. In this talk\, we will establish that suc
h root-finding algorithms exist in the real (or ra
ther\, complex) world\, and we will discuss the pr
ospects of their formalization in bounded arithmet
ic.\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR