Syllabus
Recent topics include:
- Sublinear algorithms.
- Error-correcting codes and their applications in complexity.
- Low degree polynomials and use of algebraic methods in complexity.
- Boolean complexity, lower bounds for explicit functions, formulas, branching programs.
- Lower bounds for propositional proof systems.
- Communication complexity.
- Combinatorial problems related to complexity. Expanders. Extremal combinatorics of set systems.
Annotation
Seminar on computational complexity and related combinatorial problems. Recent papers and results of the participants are presented.