> (h
/0DTimes New Roman(v0(
0 DTimes New Roman (Hebrew)(
0 DComic Sans MSn (Hebrew)(
0 B0DWingdings MSn (Hebrew)(
0 @DSymbolgs MSn (Hebrew)(
0 PDMonotype Sorts (Hebrew)(
0 c"(.lP
@n?" dd@ @@``_@,WHOOSH.WAV.WAV 10103RIFFWAVEfmt ++data~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~zvtvxz~zvrnlrvvtrpptz~xvtv~~zxvvvz~xrlhntzzvrrpprrx~j[QU_bICCYn[ICY~zlnh]_r]SUSSjzx__l~v_]drnUbnfd_]d]5=rrnj]jz~lMldrx[[_fYQfWK_xh[zx[CIjzxxdSQz_fI9WӹM;QnvK;OUx~xj]]YS~ɵlM?plM;CGpٵ[)Kh%%;xtKQS]ɖbGrlSnvz~nfS[nëx;Az=+AYݻ=/1r_
?潄W5/Czãf)/pvbMQrO=OtjdhjlG?G_ɊK3לdQCMppW;1SŷAMz/#?bx͖SAM[hvhYp~~zrvt[]ptWOUtxxd]v~vvxzd_xzh_nrSQltbdp~_lrQ_l][tf]W]~hWfpfWhnhbU[hzlSCWbYbnxpdhjvjM9Ot]GQ[dpp~hhhdpx~xh]Yntnrp]dlvjQMbvdjpzxzztljr_[r~~jb_jzxpp~~v]Whzxxzzndhpxr]Yfntzjlz~vppnrzphrxz~xtrjjtv~~vzzxrrv~xrprtzvzxvxxtx~~~~~~~zxxxxzxz~~~rrz~xz~~vtxzxz~~~zx~~zzzz~~~~~~~~zz~z~~~~zxzz~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~zz~~~~~~~~~~~~~~~~~~~~~~~~~z~~~~~~~~~~~~~~~~~~~~~~~( ( $
M)
+j
Z2P;6=8d/Ep?Z!* /5 T ## +
rXjX$123
gֳgֳ
A5% 8c8c
?1 d0u0@Ty2 NP'p<'pA)BCDES" bRbi##ff@8,,g45d5dv02p?pH<4KdKd`
0L g45d5dv0p4p\<4!d!d`
0Luʚ;2Nʚ;<4dddd{
0:2___PPT9/0?O=
Introduction
In this lecture we will study some of the relations between Boolean circuits and Turing machines:
We will define and explore the classes NC and AC
Establish a strong connection between space complexity and depth of circuits. :d* O Boolean Circuits definitions& Definition: A Boolean Circuit is a directed acyclic graph with labeled vertices:
The input vertices, labeled with a variable xi or a constant (0 or 1), and have fanin 0.
The gate vertices, have fanin k>0, and are labeled with a Boolean function on k inputs ( )  The () gate has fanin 1 always.
The output vertices, labeled output , have fanout 0.Q0ZA0ZAf4f
"
fH,f$F+ I !Boolean Circuits definitions (2)"" cSize(C) of a circuit, denotes the number of gates in a circuit C.
Depth(C) of a circuit, denotes the maximum distance from an input to an output.
A bounded fanin circuit, is a circuit with an apriori upper bound on the fanin of its AND and OR gates. An unbounded fanin circuit, is a circuit with no limitation on the fanin of its AND and OR gates.d 2f;fKf^fId a_Boolean Circuits observations
*
jAny circuit with bounded fanin K, can be transformed into a circuit with bounded fanin 2, paying only a constant factor in its depth and size.
Using DeMorgan s laws, any circuit can be modified in such a way that all the negations appear only in the input layer.
We can construct any unbounded fanin circuit, in the special form where all and gates are organized into alternating layers, with edges only between adjacent layers. 7f*f=ff+F) l yx!Families of Circuits definitions "
" <Definition: A language L is said to be decided by a family of circuits {Cn}, when Cn accepts n variables as input iff "n "x{0,1}n Cn(x)=cL(x)
Definition: Functions Depth D and size S of a family implies that
"Cn, Size(Cn) s(n)
"Cn, Depth(Cn) d(n)
Where s()S and d()Df.fffffffffff
f.ffH Q
! zLogspace uniformity Definition: A family {Cn}, is called logspace uniform if there exists a DTM, M, s.t. "n M(1n)=<Cn> and M is in space log(<Cn>)<fffffffff
fb H {Smalldepth Circuits @Motivation: A small depth circuit is a polynomialsize circuit whose depth is polylogarithmic in its sizeThat is: a circuit with size=p(n) and depth=O(logkn)
Next we show that for such circuits the unbounded fanin will not add much power.
And that such circuits capture the notion of efficient parallel computation.RM` ffff fFN G Classes NC and AC Definition: class NC
For K0, NCk is the class of languages that can be decided by families of bounded fanin, small circuits:
{Cn} s.t. size(Cn)=p(n) and depth(Cn)=O(logkn).
Definition: class AC
For K0, ACk is the class of languages that can be decided by families of unbounded fanin, small circuits:
{Cn} s.t. size(Cn)=p(n) and depth(Cn)=O(logkn).
1 1  ffff=f
ffffffff= f
fffff& ` $ c } AC = NC TTheorem: "k0 NCk ACk NCk+1
Proof:
The first inclusion is trivial
The second inclusion is easy to observe:
The fanin of ACK circuits must be bound by poly(n), thus each gate can be converted to a tree of identical gates, with fanin=2 and depth O(logn).
By Transforming all ACk gates, we get a circuit with bound fanin 2 and with a polyfactor in size and with a logarithmicfactor in depth.
This is an NCk+1 circuit .()  KffffffYfff
$$ ] 7 C e` AC0 NC1@ *Theorem: AC0 NC1
We next show a sketch for proving that the parity problem is in NC1 but not in AC0.
Definition: Parity(x1, & ,xn) i xi (mod 2)ffffff+fffffffffffffffffF ~ AC0 NC1 (2)L Claim: ParityNC1
Proof:
Parity can be computed by a binary tree of xor gates.
We then replace each xor gate with three gates:
ab=(a b) (a b)
We increased the size and depth in factors 2 and 3 respectively.
Consequently, Parity is computed by circuits of logarithmic depth, and polynomial size; thus in NC1.R <f
ffffffffffffffAfff
fFF AC0 NC1 (3)B Claim: Parity AC0
Proof (sketch):
We show that every constant depth circuit computing Parity, must have a subexponential size.Therefore, Parity cannot be in AC0 :
 First we Prove that depth 2 parity circuits must be large
 Then we prove that depth d small circuits solving parity, can be converted to d1 depth smallcircuits.Thus, contradicting the induction hypothesis.
Theorem: "d constant, a circuit computing Parity must have size exp(W(n1/(d1))).< (S K^ffff:f4f.ff
fff* AC0 NC1 (4)B vBase (d=2):
Assuming the circuit is an AND of OR gates:
 Any AND gate evaluating to 1 will determine the value of the circuit.
 Every AND must be of fanin = n, otherwise such AND gate evaluates to 1 independently of some xi
 Thus, each AND gate represents some assignment of the input variables.
There must be at least 2n1 AND gates, otherwise there is an assignment s=x1,& ,xn s.t. Parity(s)=1, of which no AND gate evaluates to 1 .t,`(( <fc ffB
`fffffffffff(F ; AC0 NC1 (5)B The Induction step:
The induction is based on the Lemma of Hastad:
Given a depth 2 circuit, say AND of ORs; if one gives random values to a randomly selected subset of variables, it is possible to write the induced circuit as OR of ANDs with very high probability.
Given a depth d circuit computing parity, we assign random values to a large number of its inputs. Consequently we obtain a simplified circuit with fewer variables; but still computing parity.
By Virtue of the lemma, we can interchange the two layers closest to the input. Then merge the two now adjacent levels with the same connective, thus decreasing the depth of the circuit to d1. A.ff
ff
fN
ffff
fAf=fff&fffb; & ~ AC0 NC1 (6)B TFormally:
On input variables x1,& ,xn the random restriction e treats each xi independently as follows:
w.p. (1e)/2 set xi=0
xi = w.p. (1e)/2 set xi=1
w.p. e leave xi as a variable
 The expected number of variables is m=ne.
 We would like to reduce the size of the transformed circuit to be smaller than exp(o(m1/(d2)))
Requesting n1/(d1) < m1/(d2)
we get n1/(d1) < m1/(d2)
thus we choose, e=n1/(d1).Ja0U ffff
ff%
5fX " % . o NC and Parallel Computation Definition (PRAM)
A PRAM machine, consists of several independent RAMs, each having a separate set of registers. In addition, there is an infinite shared memory accessible by all RAMs.
We denote as PRAM(t(),p()) the class of languages decidable by A PRAM working in parallel time t() by using p() processors.
A parallel computation is said to be efficient, if it can obtains an exponential runtime drop, in solving a problem, comparing to sequential machines.ffffff'ffffffff ffHFB n NC and Parallel Computation (2)$ Theorem: uniformNC = PRAM(polylog, poly)
The class NC captures the notion of efficient computation by PRAM machines. Similarly to the way class P captures the notion of efficiency for the RAM machines.
The class NC ignores two important aspects of parallel computation:
 Communication between processors
 The real bottleneck, which is the number of the processors. A PRAM(t(log2n),p(n)) is more likely useful than PRAM(t(logn),p(n2)). ff ff&f
R
+
ffff
fffffb
$Circuit Depth and Space Complexity% LDefinition: Depth/Size(d(),s()) is the class of all languages that can be decided by a uniformfamily of bounded fanin circuits of depth d() & size s()
Definition: Depth (d()) is the class of all languages that can be decided by a uniformfamily of bounded fanin circuits of depth d()'
8ff
ffffff8ff
fff' (Circuit Depth and Space Complexity (2) $)$) Theorem: For any integer function s()log()
NSPACE(s) Depth/Size(O(s2),2O(s))
Proof: (in the next slide we use a claim to continue the proof)
Given a NTM with s(n)space M, we construct a family {Cn} of depth O(s2) and size 2O(s) s.t.
"X{0,1}* Cx(x) = M(x)
Recall that the computation of M on x, can be represented by the configuration graph GM,x where M accepts x is the problem of connectivity between the initial configuration vertex to the accepting configuration vertex.T@ Ay P
f
ffffff8fff
ffff
f0ffff
ff * 'Circuit Depth and Space Complexity (3)($( Claim: CONN NC2
proof:
 Given a directed graph G, let A be the adjacency matrix.
 And let B = A+I (allowing self loops)
 Let B2i,j = k (Bi,k Bk,j)
B2i,j=1 iff (i,j) are connected with a path of length2
 Using logn such Boolean multiplications, we can compute the matrix Bn, which is the adjacency matrix of the transitive closure of A.
 Finally: The squaring action is in AC0, thus in NC1
Therefore, logn NC1 multiplications will be in NC2 .lfffffffffffff ffffffffffffffffff9ff'f
4
'Circuit Depth and Space Complexity (4)($( Proof (cont):
The circuit we build is a composition of two circuits.
 The first circuit, generates GM,x for input x and M (i.e. the matrix A)
Given x and M, there are 2O(s) configurations, each represented by O(s) bits; For each pair of configurations, we check if they are adjacent by comparing the contents of the work tape in the two configurations, which is a depth O(logs) operation.
;ffffff
* } 'Circuit Depth and Space Complexity (5)($( 4Proof (cont):
 The second circuit, accepts as input the matrix A, and decides the CONN problem on GM,x.
Since GM,x is a 2O(s) circuit, and using the claim, then CONN problem can be decided on GM,x indepth O(s2) and size 2O(s).
Overall, we obtain a circuit Cn in depth O(s2) and size 2O(s) s.t. Cn(x)=M(x).,i A
0ffffffff$fff fffff,ff
fff
ffb $
(Depth(d) DSpace(d)6
* Theorem: For any integer function d()log()
Depth(d) DSPACE(s)
Proof: Given uniform family {Cn}, of depth d(n), we construct a DTM d(n)space M, s.t.
"x{0,1}* M(x)=Cx(X)
The algorithm will be the composition of two algorithms, each using d(n) space.PF  ffff f fffffP*c 0Depth(d) DSpace(d) (2)L
" *
The algorithm: (given input x{0,1}n)
1. Obtain a description of Cn
List of gates and their predecessors
The description may be exponential (as the number of gates is)
2. Evaluate Cn(x)
The proof is presented by proving the following two claims:
Claim: <Cn> can be generated using O(d(n)) space.
Proof: By uniformity of {Cn}, there exists a DTM M, s.t. M(1n) = < Cn > (description of Cn), using log(<Cn>).
Since <Cn>2O(d(n)), M uses O(d(n)) space as required.DdO2 Fn:
dOffff
ff
4
#A p I A '
/ 0Depth(d) DSpace(d) (3)B
"*
Claim: Circuit evaluation for bounded fanin
circuits can be solved in space=O(circuit depth)
Proof: Given circuit C of depth d and input x, we want to compute C(x). Our implementation is recursive:
A natural recursion would be s.t. for every operation node op in the circuit we define Value(Cx,w) :
 If the node is a leaf, simply return its value.
 Value(Cx,op)= Value(Cx,v) op Value(Cx,u)
where v and u are the predecessors of op.~`j 2j F
fffX fAb ffff%ff~+ F 1 0Depth(d) DSpace(d) (4)B
"*
We represent each vertex by a path reaching it from the output vertex.
 The output vertex is represented by e, the empty string
 Then, its right predecessor by 0, and the left one by 1
Consequently, each vertex is represented by a binary string of length O(d). Where its predecessors are achieved by concatenating 0 and 1 respectively!
For a path representing a leaf or a node operation:
 If path is a leaf then return its value.
 Value(Cx,op) = Value(Cx, patho1) op Value(Cx, patho0)
! At each recursion level, path determines precisely all the previous recursion levels; Thus, space consumption is O(d).G4 Pe y Pfffffff
fffff(
fffAffffxffb
Corollary
We summarize the relation between Circuit depth and space complexity:
NC1 L NL NC2H#
ff^ P
` f3` 3f3` ___>?" dd@$?lPd@ d " @ `" n?" dd@ @@``@n?" dd@ @@``PX A @ ` `p>>
d(
ZL?f@?
Ngֳgֳ ?`
X Click to edit Master title style!! 2
H`gֳgֳ ?
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
Tgֳgֳ ?0`P
T*
Tgֳgֳ ?0P
V*
Tgֳgֳ ?0 P
T*
`jJ?f
Nvdh@? ? f;&3 6Project Overview (Standard)c @ q(
Z?@?
Z?'d@?
N$Agֳgֳ ?pA
X Click to edit Master title style!!
H
Agֳgֳ ?
pA
[#Click to edit Master subtitle style$$
TAgֳgֳ ?0`PA
T*
TAgֳgֳ ?0P A
V*
TAgֳgֳ ?0 PA
T* R
s*? f
Nvh@? ? f;&30`l(
l
l
0ԊA ?$
A
V*
l
0؎A y $A
T* d
l
c$ ?Fs A
l
0p{A ;}A
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
l
6A 6?[ A
V*
l
6A 6y [A
T* H
l0gq ? ̙33D0
(
l
C!A0 `A
^
6)`` B
H"Agֳgֳ ? ,$D0
Slides by Michael Lewin & Robert Sayegh.
Adapted from Oded Goldreich s course lecture notes by Vered Rosen and Alon Rosen.{{Cb6
(
gֳgֳFW1
?Circuit Depth &
Space ComplexityArial Black}H
0h ? f3~
pP( hH
P
P 0APp`<$0
A
P
6A <$0A
H
P0h ? f3
.< .(
<r
< S(u`
r
< SB
+<
H,1?V<
20.1.1P zE##G##E##
.<
#lAgֳgֳG\H?
\(,$D0
*2Given an assignment s{0,1}m on variables x1& x, C(s) denotes
the value of the circuit s output. By assigning to each vertex
its Booleanoperation value.8 lPPg##########m##g"## H
<0h ?.< f3
" $(
r
S`
r
S
H
0h ? f3
VNq(
x
c$*`
B
*
ZgֳgֳD?H
h
f,gֳgֳ?t
V,( lP2C"
m
Tgֳgֳ ?
q
HX1?V<
20.1.2P zE##G##E## H
0h ? f3P 8( x
8
8
NKAgֳgֳ ?`
"Boolean Circuits observations (2)#*
8
HAgֳgֳ ?
F 7
8
HQAgֳgֳ ? 0x
For any Turing machine M running on some input x{0,1}n in time TM(n),we can construct a circuit of size TM2(n) and of depth bounded by TM(n).
Circuits may be organized into disjoint layers, where each layer consists of gates having equal distance from the input vertices. Such circuit presentations capture a notion of parallel programming (more on this later).n 7fff fff$fn H
80h ? f;&3
4 ( XX
4l
4 C0L`
l
4 CL
4
H4N1?V<
20.1.3P zE##G##E## H
40h ? f;&3
~ v <(
<l
< C$Z`
l
<
CZ5
i
<
#lwgֳgֳGlH{?1
' is the description of
the circuitX(( lPe###e##e##* % p
<
f}gֳgֳ?z{YS
n!!Note that M runs in logspace of the output size, so
that we can produce circuits of superpolynomial size.:o8 lPU
io
<
Hrgֳgֳ ?A
D
DBy requiring uniformity we correlate the size and depth of a family {Cn}, which decides language L, with the complexity of the language s TM
ff
ff
ff*E F
<
#l$;gֳgֳG'H?.o,$D0
I!! Otherwise, The family of circuits with constant output (true or false)
on input 1n, can easily decide languages, even outside R; Simply by
representing the truth table of any language.ZU####g##g"## H
<0h ?/ << f;&3
h`@( @@L@
@l
@ C@`
l
@ C
@
H81?V
`20.2* zE## H
@0h ? f;&3
D8( .PP
Dl
D CD`
l
D CF
D
ZHgֳgֳ?,G
NC k NCk#### ## ########g.##*
D
Zgֳgֳ?=e
AC k ACk#### ## ########g.##*
D
H@#1?V<
20.2.1P zE##G##E## H
D0h ? f;&3
H( P
Hl
H C`
l
H Cl_
H
#lgֳgֳGPH9^?1?,$D0
.Open Questions:
 Does the hierarchy collapse?
 What s the inclusion between
NC and PH[( lPg##Jg##[ H
H0h ?H f;&3
H@(
x
c$`
0Xf
`gֳgֳ?
x
 The theorem implies that uniformAC0 P
 Whereas the question uniformNC1 ? NP is open !
a##
############
################
##c"a
H$1?V<
20.2.2P zE##G##E## H
0h ? f3
L(
Ll
L C`
l
L Ct!
H
L0h ? f;&3
P(
Pl
P C`
l
P CxW
H
P0h ? f;&3E
0Tm(
Tl
T C$:`
l
T C:!
M
T
#l)gֳgֳGHN?R
1Applies Symmetrically
for an OR of ANDs
circuit22( lP2g##*$
H
T0h ?T f;&3
@X$(
Xl
X CH`
x
X c$PIf 0
H
X0h ? f;&38
Pd`(
dl
d CdWzO
l
d CX`
r
d
fZgֳgֳf?M
\2( lPg"f F
d
#lH`gֳgֳGRH?
t,$D0
vThis is a
smallo2( lPg## H
d0h ?d f;&3
`\ (
\l
\ Ch`
l
\ Ch%
\
H1?V<
20.2.3P zE##G##E## H
\0h ? f;&3
p`(
`l
` C`
l
` Cl@
H
`0h ? f;&3
h (
hl
h Cx`
l
h Cpy1
h
H\z1?V<
`20.3* zE##
h
`Xjgֳgֳ?
NC is Depth/Size(polylog,poly)p( lP2g##
g##g##c"F
h
`gֳgֳ?
&NC Depth(polylog)( lP2g####g## g##c"*
h
#lpgֳgֳGH?
i,$D0
$ Actually Depth(d()) is Depth/Size(d(),2O(d()))
 Therefore, potentially Depth(polylog) contains languages that do not belong to NC( lPg##g##g##G####G##g##
g##g##G####G##g##o##O####O##o##Xg##o##*S 1 H
h0h ?h f;&3
l( @
ll
l C̽`
l
l Cf
H
l0h ? f;&3v
&p(
pl
p C`
l
p C"m
~
p
#lgֳgֳGH;?&W
"Corollary: NLNC2( lP
g####g##o##g## H
p0h ?p f;&3
t(
tl
t CD`
l
t CTB(
H
t0h ? f;&3
zx(
xl
x C$`
l
x CH%
x
#lUgֳgֳGH?dZ
>RWe actually proved NSPACE(s)Depth(O(s2))*( lPg## g#### g##o##g##g##* H
x0h ?x f;&3
D<(
l
 C@/`
l
 C/i

`5gֳgֳ?=
$~Lemma: Let M1, M2 be two s(n)space Turing machines. Then, there exists an s(n)space TM M that on input x outputs M2(M1(x)).t( lPGCSG##G##$G## H
0h ? f;&3
(
l
C<+`
l
C+G
H
0h ? f;&3
y(
l
C0k`
l
Ck=
Z mgֳgֳ##?
lg
#!! However, such recursion consumes space O(d2) :
There are O(d) recursion levels, where at each level
we remember a vertex name which is also O(d)\8 lPKe##m##he## $
#lsgֳgֳGH$H?
Assuming
fanin=2D( lPg##c" H
0h ? f;&3
( 0i
l
Cw`
l
C E~
H
0h ? f;&3
( {s
l
C`
l
CH
H
0h ? f;&3v,xZ{p\y+ihmI
v~>$KQ݇$
mI{e66kx0Iw#I;ym&ML I&di 4& Ӳ}]I+#tLr~{믵.MZ!}Pn*$`f"YP.mr*76TlX&
1h>l߇ߞ0BY<R)Byz+nc!eE?Ɂt66F:Wqap7_s^R ]fg?vynuZisU\mxOXo^:7 [VVM
ۀ';B]ww}@X?wzE{:@0+J#(pxLap&)HD1`HǁG2@y!Sp8)K/%ieFmpYP+qnPǽ'o8^/zeW68[փ=QݲkIl!Mți%<89v?iEͧ*J\:UujCۦѶоӁgFB"8
E\!.MXz*Bz:9t8^ibK3ELvI;9]P]#=[t$RmӡICDC$':ȕPtŲ}X;O4W䯞"fY16]7_]wީK͒.<'mPlʝQuI$xap
Nd"W0vNZ%}NS.Tʵ/S6qi=0;&A$u9?}[{z~~_KwU^{K}ӣc/߹vuoo{Gkm3&mduIX7ȯ]dOOar\'姚M9ؚI9vAcxxĔj0Sq]
;0j"~%n0Y8+us4U>e3NW]^1Ӿm\U_Fcx "U7Ko*RUCRmJ6 sH]P Uݤx^[RMc/&vlnw"{^Pr*ks)$y˔KyQЊ娰"ﱤ=/SP''
dci$zնX+V6k&U=5gD2Sع:(6fdRqޯ ٪m2dkg۵CmۤQvN)IdOtJʠLNF&2ǌf3P6u91h爑
#sy_]uod*SͧqOpjtjhJg*S)#SM]~H'c#Xg_;
7#xF4
#;5x/1c^J
R5_c)K^)O~ra&Nv
6Nr?W)RPh4ٓE8JD?Ög="Q#~ز9dz+Uj9^7_觢B//^Yf{qKJm$vè&>TM@yYB}ǿ)V(߶'xH0F"x,/^bh:'GhyXTfQ
AA{V$0{2ӇO)+++r\'aFnE9Yvo#gTuv@Ιrr+3e랐~ۅ>oUjZ; Ur@
KޱFnL%r*ׯɲg{)f%5fkel$c;1ZǪ2o*3~3
Έ<2oIӗDA
@_Cn~J"oYw6zߥM_؟(yE[
U?S
{mîs;ӽh9dd,lY
6_1+{T ~}5a/l[VzaC@aY=я 04HCQ䅐Đ5G(PEjmD%e~<>0Z1Js)M%KyALr:AY̟߬P#=8EohYytު9q9PW7ىX[Q &=Ё5+@蔢Iz>L_f:AJiUfȝ2CȟDɉ%_r_Z~Ŀ{֏AhG!1)!(n~wGhYغ:¦4!:(A##?a}KK
=64e5Fqbi귴Y<h#fXOXcy+4%/+EWjG:$GHXq~v;9
v%foCf6%U!ջV/aM({*ӷw`+{~DeL%S&3ޮ"cS_Un^G9m7ΕA1%j\>yl"57Q0n)J;_tQ#6l?շK,&lD>߭rA.St 'PMf?ؼ=Ww^FE<3J&;ffXԥmXZ`?D璩KzF>̠G2Ofij
m@jyKNvntn_ýmOt j
=zhZD3é62h۵"mU\fܴR(PO4z{@ yaԢNzۺ]H{?<4#0`f:uǀ%}'Ѡ^(MjW:#w̖f&mݽ>_nW;jtMͣ[fˍ^ D5.#J_ q{+b=j鸜k/Z?@<r*
Tv, 1ae.pp00
% #{'[)4.0
r@Oh+'00Rhp (
HT
`ltCircuit depth & sizePRobert & Mike& ZC:\Program Files\Microsoft Office\Templates\Presentations\Project Overview (Standard).potnPr Whor823Microsoft PowerPointoso@UI @=
7@@H@X' GP;
R('&@ &&#TNPP2OMi
&
TNPP &&TNPP@
'A x@(xKʦ""")))UUUMMMBBB999PP3f3333f333ff3fffff3f3f̙f3333f3333333333f3333333f3f33ff3f3f3f3333f3333333f3̙33333f333ff3ffffff3f33f3ff3f3f3ffff3fffffffff3fffffff3f̙ffff3ff333f3ff33fff33f3ff̙3f3f3333f333ff3fffff̙̙3̙f̙̙̙3f̙3f3f3333f333ff3fffff3f3f̙3ffffffffff!___www_e_e_eekekkekkekkekkekkek_e_e_eee_e_e_eee_e_e_eee_e_e_eee_e_e_eee_e_e_eee_e_e_eee_e_e_eee_e_e_eee_e_e_eee_e_e_eee_e_e_eee_e_e_eee_e_e_eee_e_e_eee_e_e_eeeeeBeeeBeeeeeeeeeeeeeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeee__eBeeBeBeeeeeeeeeeeeeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBeBeBeeeBBe_ee_eekkkekkkkekkkkek_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eee_eeeeBeeBeeeeeeeeeeeeeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeeBeeBeeeeeeeekekekekekekeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeBeeeeeeeeeeeeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeeBeeeeeeBeeeeeeeeeeeekkkkkkkkkkkkeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeekkkeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeekeekkkkkkeeeeekeeeekeekekeeeeeeekeeeeekeeeeeeekeeeeeeekeeeeeeekeeeeeeekeeeeeeekeeeeeeekeeeeeeekeeeeeeekeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeekkkkkkkkkkkkeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeekeekeekkkkkkeeekeeekeeeeekeeekeeeekeeekekekeeekeeeekeekeeekeeekeeekeeeeeeeeeeeeeeeeeeeeeeeekekkeekekkeeeekkkeeekeekeekeekeekeekeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeekkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeekkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬٬kkkkkkkekekeeekeeeeeee_eee_e_B_e_B_B_B_<_B_<_B_<<<_<<<<<<<<<<keeeeeeeeeeeBeBeBeB_B_B_B?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{}~Root EntrydO)Current UserSummaryInformation(`RPowerPoint Document(RADocumentSummaryInformation8Root EntrydO) f^nh@Current User8SummaryInformation(`RPowerPoint Document(RA _.APe D WhoPe D Who