Talks - Spring 2019

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.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator