Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> APRIL 16: THEORY CS SEMINAR
About
Undergraduate
Graduate
Research
People
News & Events
APRIL 16: THEORY CS SEMINAR
Event date: Friday, April 16, 2010, from 11:10 AM to 12:10 PM
Location: Galbraith Bldg, Rm. 221
Speaker: Pascal Koiran
Ecole Normale Superieure de
Lyon
Title: Shallow circuits with high-powered inputs.
Abstract:
A polynomial identity testing algorithm must determine
whether an input polynomial (given for instance by an arithmetic
circuit) is identically equal to 0.
Following Kabanets and Implagliazzo (2004), it has become increasingly
clear in recent years that efficient deterministic algorithms for polynomial
identity testing would imply strong lower bounds (the connection between
arithmetic circuit lower bounds and derandomization of polynomial
identity testing was foreshadowed in a 30 year old paper by
Heintz and Schnorr). This approach to lower
bounds was advocated in particular by Agrawal (2005).
In my talk I will present some further results on univariate polynomial
identity testing. I will highlight three open problems which can be
viewed as refinements of the tau-conjecture of Shub and Smale on
integer roots of univariate polynomials.
In particular, I will propose a real version of the tau conjecture.
A positive answer to any of these three problems would imply a
superpolynomial lower bound on the arithmetic complexity of the
permanent polynomial.