Course Structure
Advanced Topics in Computational Complexity
Approximation Algorithms
Randomized Algorithms
Other Techniques for Tackling Complexity
________________________________________
Advanced Topics in Computational Complexity
This part of the course will delve into the hierarchy of computational complexity. We will cover:
Various computational models
Important classes such as P, NP, PH, PSPACE, ECP, and NEXP
The role and examples of reductions between these classes
The concept of relativization (oracles)
Ladner's theorem and examples of problems like graph isomorphism (GI) and factorization
Modeling problems with Boolean satisfiability (SAT), integer linear programming (ILP), and semidefinite programming (SDP)
________________________________________
Approximation Algorithms
This section will focus on algorithms that guarantee solutions with a certain deviation from the optimal one. The topics include:
Definitions of approximation algorithms and the APX class
Design methods such as:
Greedy algorithms
Linear programming
Semidefinite programming
Polynomial-time approximation schemes (PTAS)
Algorithms with a constant approximation ratio
L-reductions within the APX class
________________________________________
Randomized Algorithms
We will explore how randomness can help in solving difficult problems. This includes:
The use of randomness for problems in the P class, for example, with the Rabin-Miller and Karger algorithms, and checking for polynomial identity
The use of randomness for approximation
The color coding method
The concept of derandomization, which converts randomized algorithms into deterministic ones
________________________________________
Other Techniques for Tackling Complexity
Finally, we will get acquainted with other approaches, such as:
Fixed-parameter tractable algorithms (FPT) and kernelization
Quantum algorithms
Circuit complexity
Exact exponential algorithms