|Course title||Theory of Computational Complexity
|Course description|| This course introduces some of the following topics: deterministic and non-deterministic Turing machine, time and space complexity, NP-completeness, polynomial time hierarchy, probabilistic computation, interactive proofs, complexity of counting, concrete models such as query complexity, communication complexity, formula complexity, branching programs and circuit complexity, quantum computation, complexity-based cryptography, randomness-related topics such as derandomness, pseudorandomness, extractors, random walks, etc.
|Semester||1 or 2|
|Grade Descriptors||A/A-: EXCELLENT – exceptionally good performance and far exceeding expectation in all or most of the course learning outcomes; demonstration of superior understanding of the subject matter, the ability to analyze problems and apply extensive knowledge, and skillful use of concepts and materials to derive proper solutions.
B+/B/B-: GOOD – good performance in all course learning outcomes and exceeding expectation in some of them; demonstration of good understanding of the subject matter and the ability to use proper concepts and materials to solve most of the problems encountered.
C+/C/C-: FAIR – adequate performance and meeting expectation in all course learning outcomes; demonstration of adequate understanding of the subject matter and the ability to solve simple problems.
D+/D: MARGINAL – performance barely meets the expectation in the essential course learning outcomes; demonstration of partial understanding of the subject matter and the ability to solve simple problems.
F: FAILURE – performance does not meet the expectation in the essential course learning outcomes; demonstration of serious deficiencies and the need to retake the course.
|Learning outcomes||At the end of the course of studies, students will have acquired the ability to
1. understand the typical complexity classes and common techniques for various reductions;
2. prove lower bounds in concrete complexity models.
(for reference only)
|Recommended Reading List||1. Computational Complexity—A Modern Approach, Sanjeev Arora and Boaz Barak, Cambridge University Press, 2009.
2. Computational Complexity: A Conceptual Perspective, Oded Goldreich, Cambridge University Press, 2008.
3. Boolean Function Complexity: Advances and Frontiers, Stasys Jukna, Springer, 2012.
|CSCIN programme learning outcomes||Course mapping|
|Upon completion of their studies, students will be able to:|
|1. identify, formulate, and solve computer science problems (K/S);|
|2. design, implement, test, and evaluate a computer system, component, or algorithm to meet desired needs (K/S);
|3. receive the broad education necessary to understand the impact of computer science solutions in a global and societal context (K/V);||TP|
|4. communicate effectively (S/V);
|5. succeed in research or industry related to computer science (K/S/V);
|6. have solid knowledge in computer science and engineering, including programming and languages, algorithms, theory, databases, etc. (K/S);||T|
|7. integrate well into and contribute to the local society and the global community related to computer science (K/S/V);|
|8. practise high standard of professional ethics (V);|
|9. draw on and integrate knowledge from many related areas (K/S/V);
|Remarks: K = Knowledge outcomes; S = Skills outcomes; V = Values and attitude outcomes; T = Teach; P = Practice; M = Measured|