Course description:
Participants are expected to attend classes and spend sometime after class refreshing what happened. Roughly 4 hours of study is required per week.
Course Goals:
To gain an understanding of some important complexity classes. (NL, NP, co-NP, PH, IP, FPT, CZK, etc.,).
Discuss how one can identify classes their favorite problem lies in.
Understand reductions between different problems.
Target group: Early stage PhD students in computer science in who hope to develop a rigorous background in complexity theory.
Prerequisites: Need to have a decent mathematical background and be able to write and understand proofs.
Has attended CS core course 1/2.
Evaluation: Assessment will be based on a final presentation by students.
Teaching format: Teaching will be in the form of blackboard lectures mostly, sometimes with slides.
ECTS: 3 Year: 2024
Track segment(s):
Elective
Teacher(s):
K. S. Thejaswini
Teaching assistant(s):
- Teacher: K. S. Thejaswini