文档介绍：THE UNIVERSITY OF CHICA GO
COMBINA TORIAL METHODS IN BOOLEAN PLEXITY
A DISSER T A TION SUBMITTED TO
THE F A CUL TY OF THE DIVISION OF THE PHYSICAL SCIENCES
IN CANDID A CY F OR THE DEGREE OF
DOCTOR OF PHILOSOPHY
DEP AR TMENT PUTER SCIENCE
BY
ANNA G AL
CHICA GO
ILLINOIS
A UGUST
A CKNO WLEDGEMENTS
First of all
I w ould lik e to thank m y advisor
J
anos Simon
His con tin ued
supp ort and atten tion has b een v ery b ene
cial for m yw ork and I learned a lot from
him
I w ould lik e to thank L
aszl
o Babai for his guidance and for all his generous help
that greatly in
uenced this w ork and m y education
The regular meetings for the last few y ears with Gyuri T ur
an
F arrokh V atan
and Sat y aV
Lok am ha v ebeenv ery motiv ating and help ed to build m y understanding
plexit y theory
I am grateful to Avi Wigderson for his kind in vitation to Hebrew Univ ersit y
Iha v e b een v ery fortunate to ha v e the opp ortunit ytow ork with him and enjo ythe
hospitalit y and excellen t researc hen vironmen t of puter Science Departmen t
at Hebrew Univ ersit y
The problems considered in Section
and in Chapter
ha v e
b een suggested b y him
and he in tro duced me in to these areas
Iha v e learned a lot from w orking with Mario Szegedy
The results in Section
are join tw ork with him
I thank Mik eP aterson and Amos Beimel for their en th usiastic collab oration
whic h led to the results in Section
Finally
Iw ould lik e to thank the Departmen t puter Science of the
Univ ersit y of Chicago for a friendly and pro ductiv een vironmen t
ii
T ABLE OF CONTENTS
A CKNO WLEDGEMENTS
ii
ABSTRA CT
v
Chapter
INTR ODUCTION
Complexit y of Bo olean functions
The basic mo del
Bo olean circuits
plexit y classes NC and AC
Bo