“You must attend the AMSI Summer School since it is highly
worth it. Not only you will enhance your knowledge and skills
in the area of mathematical sciences, but also you can broaden
your networking.”

Abdul Hadi Asfarangga, The University of Adelaide

Computational Complexity

Lecturers

Associate Professor Youming Qiao, University of Technology Sydney

Synopsis

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.

Course Overview

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

Prerequisites

  • 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.

Assessment

  • TBC

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

Associate Professor Youming Qiao, University of Technology Sydney

Youming Qiao obtained his PhD in computer science from Tsinghua University in 2012. His advisors were Andrew Yao and László Babai. After serving as a postdoc in the Centre for Quantum Technologies, National University of Singapore, Youming is currently an associate professor at the Centre for Quantum Software and Information, University of Technology Sydney. Youming works in theoretical computer science. Within this broad area, his main research interests lie in computational complexity theory and algebraic computation. He also has interests in cryptography, quantum information and computation, and group theory.