School of Computing
Queen's University

# COMPUTATIONAL COMPLEXITY CISC-876

## Fall 2018

The goal of complexity theory is to discover and quantify the amount of computational resources required to solve important computational problems and to classify problems as to their intrinsic computational difficulty. Usually the most relevant resources are computational time, space (memory size) and circuit size (hardware). The main challenge is to establish lower bounds, that is, to prove that certain problems cannot be solved without expending large amounts of resources. The P =? NP question is the most famous problem of this type and it has remained unsolved for close to 50 years. For a recent attempted proof see here.

The results of complexity theory have very practical significance. For example, modern public-key cryptography has developed advanced protocols for providing services such as secure user identification or digital cash. The security of a public-key cryptosystem is based on the hardness of some computational problem (there is no efficient algorithm for solving the problem). However, as long as we don't have lower bounds for the complexity of these problems the security of the protocols remains conditional.

### Topics

The course discusses the main complexity measures and provides an introduction to some more advanced topics in computational complexity and circuit complexity. Depending on time and interests, we can include a guided tutorial on the limits of algorithmic computation and uncomputability.

Planned topics include:

• Classical complexity classes, P=?NP
• Randomized algorithms and probabilistic complexity classes
• Interactive protocols and zero-knowledge proof systems
• Lower bounds for circuits
• Parallel complexity classes and alternation
• Communication complexity of two-party protocols
• Uncomputability (guided tutorial)

### Meeting times

• Tuesday 2:30 - 4:00 PM Goodwin 521
• Wednesday 2:30 - 4:00 PM Goodwin 521

### Prerequisites

It is expected that participants are familiar with basic definitions concerning the time/space used by an algorithm or a Turing machine. These notions will be briefly reviewed in the beginning of the course. I will suggest textbooks where you can find more detailed information.

Undergraduate students wishing to take the course should contact the instructor first.

### Evaluation

• Three written assignments: 30%. The assignments must be based on individual work.
• 90 minute closed-book quiz: 15%. The quiz will be held in class on Tuesday November 27. The quiz tests understanding of basic concepts covered in the course. Part of the questions are based on the assignments.
• Seminar presentation and research paper: 50%. Each participant is required to give a seminar presentation in class and write a survey paper on the same topic. I will suggest several possible topics for the presentations. Alternatively, you are welcome to suggest your own favorite complexity theory topic for the presentation.
• Class participation 5%. Active discussion and questions during lecture are encouraged. However, you will get the full participation mark as long as you attend all the lectures.

### Texts

There is no required textbook in the course. I will make printed course notes available. Additionally we may use some research papers.

Supplementary and background reading material for the course can be found in the following texts that are placed on reserve in the Engineering & Science Library.

• J.L. Balcazar, J. Diaz, J. Gabarro: Structural Complexity I, Springer-Verlag, 1995