Upcoming Talk

ArithmeticCircuit

Title

Speaker

Date

Time

Venue

Abstract

Polynomial Identity Testing (PIT) and Circuit Lower bound

Pranav Bisht

18th Nov, 2017

4-5 PM

KD103

PIT problem asks for an efficient algorithm to determine whether a polynomial is a zero polynomial or not, where the input polynomial is given in the form of an arithmetic circuit. On the other hand, in circuit lower bound question, our goal is to find an 'explicit' polynomial family which does not have any 'small' size circuit. The talk is based on the connection between PIT and circuit lower bound.

Our talk will mainly cover the paper by Kabanets and Impagliazzo, 2003 (see the link given below). Their result essentially implies that proving PIT in P is equivalent to proving circuit (boolean or arithmetic) lower bound for complexity class NEXP. The talk assumes no background in the PIT problem and circuit lower bound.


http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=6453645CFC8D962387CBC7EE64F92DF0?doi=10.1.1.626.9842&rep=rep1&type=pdf

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