My PhD work and the resulting thesis was in the field of Algebraic Complexity Theory, where we study polynomials and problems which can be solved by computing a particular polynomial. Polynomials can be used to model common mathematical problems (as an easy example, adding two integers can be represented by x + y where x and y can be substituted by any two integers we like). A question we like to ask in Algebraic Complexity Theory is how hard a mathematical problem can a given collection of polynomials represent?
Studying the last question in the previous paragraph has given algebraic complexity theorists a very good view of how powerful certain kinds of polynomials are and the difference in power between any two collections (or classes) of polynomials. However, recent advances have shown that other than the established methods of exploring these questions, a study of the mathematical properties of polynomials can also be immensely useful. My postdoctoral research was in this sub-area of Algebraic Complexity Theory.
In these papers, polynomials have been represented by directed acyclic graphs. I would like to emphasise that most of my research involved looking at graphs, identifying perfect matchings in a graph or studying trees. The mathematics most frequently used in these papers is basic linear algebra, probability and combinatorics.
PhD Thesis, On Lower Bounds and PIT for Parameterized Algebraic Models
A polynomial is usually expressed as a sum of product of input variables and each of these products of variables is called a monomial. The degree of a polynomial is the number of variables in its largest monomial, for example, xy + z has degree 2. In my thesis, we studied polynomials on n input variables whose degree, k, was restricted to be less or equal to a function of n that is much smaller than n, for example k = O(log n). We studied and concluded that such polynomials were much, much less powerful compared to the case where degree is not restricted.
Postdoc Publication, Degree-restricted strength decompositions and Algebraic Branching Programs
In this paper, we study polynomials that can be represented by a layered directed acyclic graph (DAG) where the input variables are nodes with in-degree 0 and the output node is an out-degree 0 node that represents the polynomial. We explore some mathematical properties of the polynomials that arise because they can be represented by a layered DAG. We use these properties to study the hardness of problems these polynomials can encode.
PhD Publication, Limitations of Sums of Bounded-Read Formulas
Some polynomials can be represented by trees where each input variable can occur as multiple leaf nodes and the root of the tree represents the final form of the polynomial. In this article, we studied a subset of such polynomials where each input variable can occur as at most k leaf nodes, where k is a constant greater than zero.
PhD Publication, On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models
Here, we studied polynomials where each variable occurs only once in a monomial, for example, xy + yz + xz. It is interesting to note that we constructed perfect matchings to show how weak these polynomials are.
PhD Publication, A note on parameterized polynomial identity testing and hitting-set generators
The main result of this paper shows that if we have, (1) a matrix whose entries are polynomials on n variables and degree k < n and (2) a special kind of map, applying the map on the input matrix produces a matrix with this property: If the input matrix had rank (i.e., number of linearly independent rows) R, the output matrix has rank O(R).
PhD Publication, On Constant Depth Circuits Parameterized by Degree: Identity Testing and Depth Reduction
An old result in my area shows that if the maximum path length in directed acyclic graphs used in the representation of a polynomial is fixed to be 4, they can still represent all polynomials. We show that if we restrict the in-degree of each node in the DAG to be small, then the DAG needs to be of a really large size (number of nodes) to represent certain hard-to-compute polynomials.
While completing my course credits, I mainly took courses pertaining to theoretical computer science. While I do feel that might have been limiting in some sense, it also allowed me sufficient time to take in theorems that, at first glance, seemed intimidating. I prefer absorbing new concepts through considerable amount of reflection and practice, and I noticed I was not alone in this. When I was a fresher at IIT Madras, I had to quickly get comfortable with mathematical rigour that is necessary to understand theoretical CS courses.
So I enjoyed being a TA for the same courses later, where I could guide fresh grad students who had the same problems as I did, to at least see why the subject matter was exciting. Irrespective of whether I made any visible difference, I learnt a lot about inter-personal skills in the process and became better at explaining concepts.
Following are the lists of courses I was a TA for.
I was a Teaching Assistant for the following courses:
