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