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.