Polynomial Identity Testing (PIT) and Circuit Lower bound
18th Nov, 2017
PIT problem asks for an efficient algorithm to determine
whether a polynomial is a zero polynomial or not, where the input
polynomial is given in the form of an arithmetic circuit. On the other
hand, in circuit lower bound question, our goal is to find an 'explicit'
polynomial family which does not have any 'small' size circuit. The talk
is based on the connection between PIT and circuit lower bound.
Our talk will mainly cover the paper by Kabanets and Impagliazzo, 2003
(see the link given below). Their result essentially implies that proving
PIT in P is equivalent to proving circuit (boolean or arithmetic) lower
bound for complexity class NEXP. The talk assumes no background in the PIT
problem and circuit lower bound.