ICTS

We consider the problem of classifying polynomials according to difficulty of computing them. We argue that this approach gives better classification of polynomials according to their properties compared with the usual ones  like degree or sparsity. After giving the definition, we  identify two classes of  polynomials that give rise to the central question in algebraic complexity theory and introduce the Polynomial Identity Testing (PIT) problem which has come to play a key role in resolving this question. Finally, we summarize the progress made in the past two decades in solving the PIT.