Algebraic and Combinatorial Circuits - Models of Computation: Exploring the Power of Computing - page 239

The function g s is associated with the s th step. The identity function with value v is
associated with the assignment statement ( r READ v ) . Associated with the computation step
( s OP i ... k ) is the function g s = OP ( g i , ... , g k ) ,where g i , ... , g k are the functions
computed at the steps on which the s th step depends. If a straight-line program has n inputs
and m outputs, it computes a function f :

m .If s 1 , s 2 , ... , s m are the output steps,
then f =( g s 1 , g s 2 , ... , g s m ) . The function computed by a circuit is the function computed
by the corresponding straight-line program.
In the example above, g 11 = f + , ω 2 ( g 5 , g 7 )= g 5 + g 7 ω 2 ,where g 5 = f + , ω 0 ( g 1 , g 2 )=
a 0 + a 2 ω 0 = a 0 + a 2 and g 7 = f + , ω 0 ( g 3 , g 4 )= a 1 + a 3 ω 0 = a 1 + a 3 .Thus,

n

A →A

g 11 = a 0 + a 1 ω 2 + a 2 + a 3 ω 2

which is the value of the polynomial p ( x ) at x = ω 2 when ω 4 = 1:

p ( x )= a 0 + a 1 x + a 2 x 2 + a 3 x 3

The size of a circuit is the number of operator statements it contains. Its depth is the
length of (number of edges on) the longest path from an input to an output vertex. The basis
Ω is the set of operators used in the circuit. The size and depth of the smallest and shallowest
circuits for a function f over the basis Ω are denoted C Ω ( f ) and D Ω ( f ) , respectively. In this
chapter we derive upper bounds on the size and depth of circuits.

6.2 Mathematical Preliminaries
In this section we introduce rings, fields and matrices, concepts widely used in this chapter.

6.2.1 Rings and Fields
Rings and fields are algebraic systems that consists of a set with two special elements, 0 and 1,
and two operations called addition and multiplication that obey a small set of rules.

DEFINITION 6.2.1 A ring R is a five-tuple ( R , + , ∗ , 0 , 1 ) ,where R is closed under addition
+ and multiplication ∗

(that is, +: R 2

→ R and ∗ : R 2 → R )and + and ∗

are associative

(for all a , b , c

∈ R , a +( b + c )=( a + b )+ c and a ∗ ( b ∗ c )=( a ∗ b ) ∗ c ). Also, 0 , 1 ∈ R ,

where 0 is the identity under addition (for all a

∈ R , a + 0 = 0 + a = a )and 1 is the identity

under multiplication (for all a

∈ R , a ∗

1 = 1

∗ a = a ). In addition, 0 is an annihilator

under multiplication (for all a

∈ R , a ∗

0 = 0

∗ a = 0 ). Every element of R has an additive

inverse (for all a

∈ R , there exists an element − a such that ( − a )+ a = a +( − a )= 0 ). Finally,

addition is commutative (for all a , b

∈ R , a + b = b + a ) and multiplication distributes over

addition (for all a , b , c

∈ R , a ∗ ( b + c )=( a ∗ b )+( a ∗ c ) and ( b + c ) ∗ a =( b ∗ a )+( c ∗ a ) ).

Aringis commutative if multiplication is commutative (for all a , b

a ). A field
is a commutative ring in which each element other than 0 has a multiplicative inverse (for all
a

∈ R , a ∗ b = b ∗

= 0 , there exists an element a − 1 such that a a − 1 = 1 ). ∈ R , a ∗

Let ￿ be the set of positive and non-negative integers and let + and ∗ denote integer

addition and multiplication. Then ( ￿ , + , ∗ ,0,1 ) is a commutative ring. (See Problem 6.1 .)

Similarly, the system ( { 0, 1 } , + , ∗ ,0,1 ) ,where + is addition modulo 2 (for all a , b ∈{ 0, 1 } ,

a + b is the remainder after division by 2 or the EXCLUSIVE OR operation) and ∗ is the AND