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.2-3, 10.4-6, Chap. 16, Sects.
20.8-9, 24.4, 29.3)--it can be used as a main text for a core 1-2 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.
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
(in order the corresponding note was written)
Subbotovskaya, Spira, Nechiporuk, Andreev; material to Sect. 15.2.2 and
P is not equal to NP\cap co-NP if we measure the
the depth ;material to Sects.10.4, 14.4
Lower bounds for R-way branching programs working in
linear time; a simple proof of the Ajtai-type lower bound for nondeterministic
programs in the case of large R via easy counting; material to Chaps. 1-2
A shorter exposition is in this note.
It uses Theorem 22.2 of Beame, Saks and Thathachar from the book.
circuits with real-valued gates
material to Sec. 10.6
proofs of the weak pigeonhole principle
Recent impressing development made by R. Raz and A.Razborov; material
to Sect. 4.8 and Chaps. 18-19.
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 m-n is, the ``more true''
the principle is, and it could well be that its negation then has a short
Resolution proof. It was a long-standing problem whether this intuition
is true for m> n2 . This problem was
recently solved by Ran
Report Nr. 21, 2001) : for any m>n, every Resolution proof of PHP(m,n)
has length exponential in n. Shortly after Alexander
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.
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 n-O(loglog n) negations.
complexity and monotone depth
Result of Karchmer and Wigderson that the communication complexity of a
particular minterm-maxterm 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.
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