Computer Science Colloquia: Sun, Feb 26 at 11:00 - Amir Shpilka
Niv Buchbinder
Dear all,
Next week we are happy to have Amir Shpilka from Faculty of Computer Science, Technion.
You can view the upcoming talks of the seminar at:
See you,
Niv Buchbinder.
%%%%%%%%%%%%%%%%%%%%%%
Computer Science Colloquia - Open University of Israel
%%%%%%%%%%%%%%%%%%%%%%
Time: Sunday, February 26, at 11:00-12:00
Place: Visitor center 194, Open University.
Speaker: Amir Shpilka, Faculty of Computer Science, Technion.
-------
Title: Polynomial Identity Testing.
-----
Abstract:
Polynomial Identity Testing (PIT for short) is the problem of efficiently and deterministically deciding whether a given arithmetic circuit computes the zero polynomial (intuitively, an arithmetic circuit is a "program" that only uses the arithmetic operations +,*). This is one of the most fundamental problems in computational complexity and it is strongly related to the problem of proving lower bounds for arithmetic circuits.
In this talk I will survey several results on the PIT problem. Specifically I will discuss the relation between PIT and circuit lower bounds, explain the importance of PIT in the bounded depth model and give an overview of the ideas behind several recent PIT algorithms.