School of Computing
COMPUTATIONAL COMPLEXITY CISC-876
Note: Because of the way the course is offered,
at most 20 students can take the course. Until Sept. 20
preference in registration
is given to students from the School of Computing.
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.
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
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.
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
Planned topics include:
For more information about the course please contact the
- 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)
- Tuesday 1:00 - 2:30 PM Goodwin 521
- Thursday 12:30 - 2:00 PM Goodwin 521
If you would like to take the course
and cannot attend the first class, please contact
the instructor before the first class
concerning your schedule.
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 reviewed in the
beginning of the course.
Undergraduate students wishing to take the course should contact
the instructor first.
- Four written assignments: 40%. The assignments
must be based on individual work.
- Seminar presentation and
research paper: 55%. 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.
There is no required textbook in the course. I will make
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,
- C.H. Papadimitriou: Computational Complexity, Addison-Wesley,
- U. Schoning, R. Pruim: Gems of Theoretical Computer Science,
- M. Sipser: Introduction to the Theory of Computation,