we shall use very much the excellent book Complexity of Boolean Functions
by Ingo Wegener (the so called "Blue Book").
The book can be downloaded for the personal use.
Requirements:
In order to pass the course it is necessary to fulfil the following conditions:
pass the final written test
or solve some "take home exam"
I prefer the second option.
The test will check understanding, skills and ability of problem solving.
It will consist of short problems (almost a test question)
that will demand certain creativity.
It is not necessary to remember details of algorithms, protocols, technical manuals, ...
but it will be necessary to understand them.
Goals:
The lecture has two goals:
learn advanced methods concerning computational complexity in the non-uniform setting,
learn some lower bound techniques,
get some skill for designing efficient algorithms for the circuit model.
Prerequisitives:
standard knowledge concerning algorithms and data structures