Special Interest Group on Theoretical Aspects of Computer Science was born out of an effort to bring together people interested in areas of Theoretical Computer Science. It is a platform for students and faculty members to come together and share their excitement in the area. The group aims at organizing problem solving sessions, seminars and guest lectures.
KD103, 5 pm, Friday 2nd September
Read Once ABPs (RO) are polynomial computational models where the order of variable multiplication is crucial. Though highly restrictive, they are one of the few models for which algebraic lower-bounds results have been known for a while. This talk will discuss the lower bounds of a natural generalisation called the sum of RO.
We will explore a well-known technique of proving algebraic lower bounds called the Partial Derivative method, which could be a topic of general interest for those interested in complexity theory.
The talk is based on the work of V Arvind and S Raja from 2015 - “Some Lower Bound Results for Set-Multilinear Arithmetic Computations”.
Coordinates: KD103, 3 PM 25th Oct 2018
Polynomial Identity Testing (PIT) is a fundamental problem in theoretical computer science . The problem is about finding an efficient algorithm to test if a given algebraic expression (for example, x^2-y^2=(x+y)(x-y) ) is an identity (LHS=RHS). Equivalently, the problem is to test whether a given algebraic formula computing a multivariate polynomial is identically zero or not. It may seem to be a trivial problem, as we can expand the polynomial, compute all its coefficients and check if they are zero. This is a correct algorithm, but the running time is exponential as there are exponentially many monomials in a generic n-variate degree d polynomial. A simple idea (check if the polynomial is zero at a random point) gives a more efficient (randomized polynomial time) algorithm, but the algorithm may mistakenly output zero for a non zero polynomial. Luckily the probability of error is really small, so this algorithm works in practice.
Can we give a deterministic polynomial time algorithm? There is strong evidence that there exists such an algorithm. Finding a solution would be a major breakthrough as it would solve several problems in computer science.
Last decade has seen continuous progress in this area, several special cases are now solved and strong reduction results are known. In this workshop we will start from the basics and go on till we see a few state of the art results. The prerequisite for understanding the talks is minimal, basic understanding of linear algebra and algorithms should be sufficient.
References: