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.

Any comments and corrections, as well as suggestions on what topics should be also worth to include, are welcome!

Single topics
(in order the corresponding note was written)

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

 
2. decision trees 


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

 
3.  a time-space trade-off


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 (counting)

A shorter exposition is in this note. It uses Theorem 22.2 of Beame, Saks and Thathachar from the book.


 
4. monotone circuits with real-valued gates


material to Sec. 10.6

 
5. resolution 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> n² .    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.

 
6. 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 n-O(loglog n)  negations.

 
7. communication 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) ²   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


 
8. 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.