Information Technology Reference
In-Depth Information
Chapter 7
Progress on Polynomial Identity Testing-II
Nitin Saxena
To my grand-advisor Professor Somenath Biswas
Abstract
We survey the area of algebraic complexity theory; with the focus being
on the problem of polynomial identity testing (PIT). We discuss the key ideas that
have gone into the results of the last few years.
·
·
·
·
·
Keywords
Arithmetic circuit
Identity testing
Hitting-set
Rank
Lower bound
·
·
·
Jacobian
Concentration
Shift
Morphism
Mathematics Subject Classification (2010)
Primary 68Q25, 68W30, Secondary
12Y05, 13P25
7.1 Introduction
Algebraic complexity theory is the study of computation via
algebraic
models, hence,
algebraic techniques. In this article we work with only one model—
arithmetic circuit
(in short,
circuit
). A circuit
C
(
x
1
,...,
x
n
)
, over a ring
R
, computes a polynomial
. Its description is in the form of a rooted tree; with the
leaves
having the variables or constants as input, the internal
nodes
computing addition or
multiplication, and the
root
having the
f
as output. The edges in
C
, called
wires
,
carry the intermediate polynomials and could also be used to multiply by a constant
(from
R
). By the
size
, respectively the
depth
,of
C
we mean the natural notions
(sometimes to avoid “trivialities” we might want to take into account the bit-size
needed to represent an element in
R
).
f
in
R
[
x
1
,...,
x
n
]
