Upcoming Talk

ArithmeticCircuit

Title

Speaker

Date

Time

Venue

Abstract

A Bootcamp on polynomial identity testing

SIGTACS

Starts on 25th Oct, 2018

Schedule

KD102/103

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:

Who are we???

SIGTACS - 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.


What we do???

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.

What we like???

Algorithms, Combinatorics, Cryptology, Quantum Computing, Graph-Theory, Information Theory, Game-Theory, Computational Complexity.


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator