Black box polynomial identity testing of generaliz

Authors: Zohar S Karnin Amir Shpilka

Publish Date: 2011/09/08

Volume: 31, Issue: 3, Pages: 333-

PDF Link

Abstract

A deterministic blackbox identity testing algorithm for ΣΠΣk dρ circuits that runs in quasipolynomial time for ρ=polylogn+d In particular this gives the first blackbox quasipolynomial time PIT algorithm for depth3 circuits with k multiplication gatesOur results give the first subexponential blackbox PIT algorithm for circuits of depth higher than 2 Another way of stating our results is in terms of test sets for the underlying circuit model A test set is a set of points such that if two circuits get the same values on every point of the set then they compute the same polynomial Thus our first result gives an explicit test set of quasipolynomial size for ΣΠΣk dρ circuits when ρ=polylogn+d Our second result gives an explicit polynomial size test set for readk depth3 circuitsThe proof technique involves a construction of a family of affine subspaces that have a rankpreserving property that is inspired by the construction of linear seeded extractors for affine sources of Gabizon and Raz 9 and a generalization of a theorem of 8 regarding the structure of identically zero depth3 circuits with bounded top fanin

Keywords: