


Speaker: Anamay Tengse
Affiliation: Reichman University, Herzliya
Date/Venue: 18 April (Thursday), 10 AM.
Title: Equations for efficiently computable polynomials
Abstract: Algebraic circuits are a natural model for computing
polynomials, as they essentially capture the minimum number of
sums and products required to evaluate a polynomial at any given
input. In algebraic complexity theory, circuits are used to study
how the cost of computing a polynomial varies as a function of its
number of variables. For instance, the nxn symbolic determinant has
a cost that is a polynomial in n, and is therefore 'efficiently
computable'. A central object of interest here, is the class
of (sequences of) polynomials that are efficiently computable.
The 'algebraic P vs NP' question, asks whether there are 'explicit' polynomials
that are not efficiently computable. This question was posed in a work of
Valiant's in 1979, and remains open to this date. In fact, the best 'lower
bound' against circuits is Omega(n log n), which is a result from 1983.
A lot of works have therefore focussed on more structured forms of
circuits, hoping that the techniques there could eventually be generalized.
Superpolynomial lower bounds are now known against many of these
structured models. However, since these results have not yet lead to any
better lower bounds against general circuits, some recent works have
studied a 'metaquestion': are these techniques fundamentally incapable of
leading to circuit lower bounds?
In particular, the works of Forbes, Shpilka and Volk (2018), and Grochow,
Kumar, Saks and Saraf (2017), observed that most of the current techniques
in fact yield 'efficiently computable equations' for the sets of
polynomials that are computable by the corresponding models. A nautral
question therefore, is whether there are such equations for circuits. In
joint works with Chatterjee, Kumar, Saptharishi and Ramya, we shine some
light on the classes that have (or do not have) such efficiently computable
equations. In the talk, we will first briefly introduce the relevant
concepts from algebraic complexity, and then go over some of our findings