Summer Term 2015
This is a selected topic course in area C (Discrete Mathematics) of the Master's Program in Mathematics. Basic knowledge in combinatorial algorithms and complexity theory is required.
This course covers the following topics: Boolean function complexity, algorithms for constructing fast and small Boolean circuits in chip design.
This course is in English. It will cover contents from different books, as well as many results that cannot be found in any text book yet. Recommended books covering some of the contents are
- I. Wegener: The Complexity of Boolean Function ("The Blue Book"). John Wiley & Sons, 1987 (free PDF).
- S. Jukna: Boolean Function Complexity. Springer, 2012.
- S. Arora, B.Barak: Computational Complexity. Cambridge University Press, 2009.
- J. E. Savage: Models of Computation: Exploring the Power of Computing. Addison-Wesley, 1997. (free PDF).
| Class Hours: | Tuesdays, 10-12 am (10:15-12:00) |
| Room: | Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2) |
| Oral Exams: | to be scheduled |
Prof. Dr. S. Held