Upcoming Talk

ArithmeticCircuit

Title

Speaker

Date

Time

Venue

Abstract

One Way Functions and Algebraic Complexity

Amit Kumar Sinhababu

10nd January 2019

5:00-6:00 PM

KD103

Whether checking a solution of a computational problem is easier than computing a solution is captured by the famous P vs NP question. Valiant asked a related question, whether any string function, for which it can be checked in polynomial time whether it takes a given value, can also be evaluated in polynomial time. In complexity theory (Boolean)/cryptography, the answer is expected to be negative, as it would rule out the existence of one way functions otherwise. But in the algebraic complexity setting, the answer is expected to be positive. In this talk, we present results due to Sturtivant and Zhang (FOCS '90) and Burgisser (FOCS' 01) that partially resolve the above question in algebraic setting. The question is related to two concrete problems about polynomials and arithmetic circuits (1) Given an invertible polynomial map given as a small arithmetic circuit, whether its inverse map also has a small circuit (2) Given a reducible polynomial computed by an arithmetic circuit, whether its factors of low degree have small sized arithmetic circuits. For both the problems, the key tool used is Newton iteration for root finding.

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