Alladi Ramakrishnan Hall

On verifying proofs in constant depth, and polynomial identity testing

Karteek Sreenivasaiah

HBNI PhD defense

In this talk we will see an overview of the thesis work comprising of two different themes: Verifying proofs in constant depth,and Polynomial Identity Testing.

In the first part, we look at a computationally restricted form of proof systems and study their capabilities and limitations. A proof system for a language L is a function f such that Range(f)=L. The restriction we study is proof systems computable by NC0 (constant depth, constant fan-in) circuits. We will see a lower bound argument and some constructions of NC0 proof systems.

In the second part, we study the problem of testing if an input arithmetic formula computes an identity. We look at the case of read-restricted formulas where the input formula is allowed to read any variable at most 3 times. We explore a special case of read-4 and show a hardness of representation result against a sum of Read-Once formulas that are not allowed to have constants occurring in their leaves.