Tomáš Jirotka

Jirotkova bakalářská práce "Složitost booleovských funkcí" s několika drobnými opravami - originál je možno získat v Knihovně MFF UK Praha. (The rest of this article is in English.)

Tomáš Jirotka's bachelor thesis "Complexity of Boolean Functions". I have additionally corrected a couple of tiny errors - the original thesis is saved in the Library of the Faculty of Mathematics and Physics, Charles University in Prague. (Actually they should post it on the web in several months.) The work was supervised by Prof. Jan Krajíček DrSc. It is written in Czech language, but for English speaking reader we present the following information. Each topic has some original paper listed in section 6 References. So one can use the thesis as a source of useful links.

Abstract. The paper is concerned with the circuit complexity of boolean functions. In the first part we present some general results, which are still not strong. To solve the P versus NP problem we would like to obtain super-polynomial lower bounds, while we have only linear ones. In the next chapters we introduce some special cases of circuits such as monotone and bounded depth circuits, for which the contemporary lower bounds are even exponential. Unfortunately that is not sufficient. The paper does not contain any new results and we only summarize the most important facts known to us.

Contents.

1. Introduction
2. Boolean functions and circuits
   1. Basic notions and definitions
   2. Circuit complexity
3. Circuits with bounded depth
   1. AC, NC hierarchy
   2. Hastad's switching lemma
   3. Lower bound for parity function
   4. AC0 reducibility
4. Monotone circuits
   1. Lower bound for clique
   2. Monotone projections
   3. Relation between monotone and non-monotone circuit complexity
5. Conclusions
6. References

PDF 453 kB (written in Czech)

Any comments and suggestions are welcome!