NOTE: This is no more actual ... Meanwhile the whole
this "additional stuff"
grew to the book " Boolean Function Complexity". Check my homepage for a draft version.
Old stuff still remains here ...
The book is designed so that ignoring more specific applications
in the theory of computing (like Sects. 4.8, 6.23, 10.46, Chap. 16, Sects.
20.89, 24.4, 29.3)it can be used as a main text for a core 12 semester
course in combinatorics and/or discrete mathematics for undergraduates
.
On the other hand, it also contains ample material for a compact
1 semester advanced course in computational complexity for
graduates (with the focus on proving lower bounds)..To keep the
size of the book within reasonable limits, some of the applications are
only sketched by proving the underlying key combinatorial lemma(s). To
facilitate the design of such a course, I am going to collect here draft
notes containing more detailed description of these applications, as
well as new results obtained after the book was released.
Any comments
and corrections, as well as suggestions on what topics should be also worth
to include, are welcome!
All topics (with references) as one PostScript
file or as one PDF file
Single topics
(in order the corresponding note was written)

boolean
formulas

Subbotovskaya, Spira, Nechiporuk, Andreev; material to Sect. 15.2.2 and
Chap. 20

decision
trees

P is not equal to NP\cap coNP if we measure the
size, not
the depth ;material to Sects.10.4, 14.4

a
timespace tradeoff

Lower bounds for Rway branching programs working in
linear time; a simple proof of the Ajtaitype lower bound for nondeterministic
programs in the case of large R via easy counting; material to Chaps. 12
(counting)
A shorter exposition is in this note.
It uses Theorem 22.2 of Beame, Saks and Thathachar from the book.

monotone
circuits with realvalued gates

material to Sec. 10.6

resolution
proofs of the weak pigeonhole principle

Recent impressing development made by R. Raz and A.Razborov; material
to Sect. 4.8 and Chaps. 1819.

The (negation) of the pigeonhole principle PHP(m,n) asserts that, if
m>n then m pigeons cannot sit in n holes so that each pigeon is alone in
its hole. The larger the difference mn is, the ``more true''
the principle is, and it could well be that its negation then has a short
Resolution proof. It was a longstanding problem whether this intuition
is true for m> n^{2} . This problem was
recently solved by Ran
Raz (ECCC
Report Nr. 21, 2001) : for any m>n, every Resolution proof of PHP(m,n)
has length exponential in n. Shortly after Alexander
Razborov (ECCC
Report Nr. 55, 2001) has found another and much simpler proof, which
we present in this note . This proof has an advantage that it can
be extended to even weaker versions of PHP as well as to other principles.
For more information, visit Razborov's home
page or take a look at the slidesof
his recent survey talk.

the
mystery of negations in computing

The effect of NOT gates on circuit complexity (Markov, Fischer, and me);
material to Chap. 9 and Sect. 10.6

In 1957 A. Markov has made an intriguing observation that every circuit
on n variables can be simulated by a circuit with at
most log (n+1) negations. In 1974 M.
Fisher has shown that this can be done by only polynomial increase
in size. Thus, any function in NP which cannot be computed by a circuit
with log (n+1) of negations in polynomial size would
separate P from NP. In this note we discuss these results. We then exhibit
an explicit monotone function in n variables that belongs
to NP but cannot be computed by a circuit of polynomial size if we allow
only log nO(loglog n) negations.

communication
complexity and monotone depth

Result of Karchmer and Wigderson that the communication complexity of a
particular mintermmaxterm game coincides with the depth of boolean circuits.
A lower bound of Grigni and Sipser on the FORK game. An (log
n)^{ 2} lower bound on the depth of any monotone circuit
recognizing whether a given directed graph on n+2 vertices with two specified
vertices s and t has a path from s to t. Material to Sect. 15.2 and Chap.
18

more
on rank arguments

Recent observation of P. Pudlak that superpolynomial lower bounds on the
size of monotone span programs can be obtained via very simple rank argument.
Answer to an open problem 1 on page 216 of the book (A. Gal). Material
to Sect. 15.2 and Chap. 16.
Last modified: September 23 2002
Return to the
home page of the book