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.
Super-polynomial 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 'meta-question': 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