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:
Coordinates: KD102, 5 PM 14th Feb 2018
The following is the tentative syllabus. I will often follow Salil Vadhan’s survey but not always.
Coordinates: KD102, 5 PM 6th Jan 2018
Cryptographic hash functions is one of the main component of the modern cryptography, which has practical applications in providing message integrity, authentication, digital signatures and various others securities.
SIGTACS is oragnizing a lecture series on the Cryptographic hash functions which will cover the following topics.
Coordinates: KD102, 4 PM 20th Jun 2017
In this course, we will consider mathematical objects known as lattices. More recently, lattices have become a topic of active research in computer science. They are used as an algorithmic tool to solve a wide variety of problems, they have many applications in cryptography and cryptanalysis and they have some unique properties from a computational complexity point of view. Classes will commence on 29th May. These are the topics that will be covered in the next 2 weeks.