Algebraic Complexity Theory is a field in which one studies complexity theoretic questions surrounding algebraic objects. In this talk we will be broadly discussing two such problems.
The first problem is showing lower bounds for explicit polynomials against various algebraic computational models. The most natural and well studied models of computation are algebraic circuits, algebraic branching programs (ABPs) and algebraic formulas. With respect to proving lower bounds against these models, we show the following results.
1. Any algebraic branching program computing \sum_{i=1}^n x_i^n must have at least n^2 vertices. The previous best known lower bound was \Omega(n log n) on the number of edges for the same polynomial [Baur-Strassen].
2. Any formula computing the elementary symmetric polynomial of degree 0.1n must have at least n^2 vertices. The previous best lower bound for any multilinear polynomial was \Omega(n^2/log n) [Nechiporuk, Kalorkoti]. It can also be shown that previous known methods can not prove a bound better than \Omega(n^2/log n) for any explicit multilinear polynomial.
This is joint work with Mrinal Kumar, Adrian She and Ben Lee Volk.
Along with proving lower bounds against these models, studying their relative powers is also an important problem in algebraic circuit complexity. It is known that formulas can be efficiently simulated by ABPs and checking whether the converse of this statement holds is a central question in the field. We make progress towards solving this problem in the non-commutative setting, where we show a tight super-polynomial separation between ABPs and some structured formulas.
The second problem that we are interested in relates the questions of checking whether a given algebraic compuational model is computing the zero polynomial or not and checking whether a given set of polynomials is algebraically independent or not. The connection between these questions is via the notion of Faithful Homomorphisms. Although construction of faithful homomorphisms were known when the underlying field had characteristic zero [Beecken-Mittman-Saxena, Agrawal-Saha-Saptharishi-Saxena], they were not known in the setting where the underlying field had finite characteristic since efficient algorithms to check algebraic indepndence were not known in this setting. Following up on the work of Pandey, Saxena and Sinhababu, we construct faithful homomorphisms over fields of finite characetristics in some restricted settings and as a consequence show efficient polynomial identity tests for related models of computation. This is joint work with Ramprasad Saptharishi.
