Associate Professor Youming Qiao, University of Technology Sydney
Computational complexity studies algorithmic problems in terms of the resources, such as time and memory, required to solve them. Since the introduction of the famous P vs NP problem in the 1970s, this theory has evolved into a major new mathematical program in the 21st century, providing insights into practical computational paradigms and tasks such as randomised algorithms, approximation algorithms, average-case algorithms, cryptography, and quantum algorithms.
This course is an introduction to computational complexity, with a focus on those mathematical theories developed to understand the computational paradigms and tasks described above. Efforts will be made to highlight connections to other branches of mathematics such as combinatorics and algebra.
Topics covered in this course include:
- Some basics: Turing machines, circuits, and NP
- Randomised algorithms and complexity
- Interactive proofs: another generalisation of NP
- Approximation algorithms and complexity
- Average-case algorithms and complexity
- Algebraic algorithms and complexity
- Quantum algorithms and complexity
- Pseudorandomness, zero-knowledge, and cryptography
- Students taking this course will have ideally seen basic combinatorics and discrete probability (as usually covered in a first discrete mathematics course), and linear algebra.
- Familiarity with the basics of theory of computing and/or algorithm design would be helpful, but not necessary.
- 4 quizzes 5% each (20% total)
- 3 assignments 10% each (30% total)
- Take home exam 50%
(may be subject to change)
- For those completing the subject for their own knowledge/interest, quizzes must be completed as an attendance requirement
Resources/pre-reading (if available)
There is no set text book for this course, and full lecture notes will be provided. However similar material to that covered can be found in:
- Arora & Barak (2009): Computational Complexity: A Modern Approach. Cambridge University Press.
- Wigderson (2019): Mathematics and Computation: A Theory Revolutionizing Technology and Science. Princeton University Press.
- Goldreich (2008): Computational Complexity: A Conceptual Perspective. Cambridge University Press.
Not sure if you should sign up for this course?
Take this quiz and look at some of the expected foundational skills in this topic