Com­ple­xi­ty Theo­ry

News

  • There will be no tutorial on 25.01.19.
  • There will be no exercises in the tutorial on 29.01.19. Instead, it will be open for questions. If you have any extensive or highly technical questions, please eMail these to Sascha Brauer (see box on the right) ahead of the tutorial.
  • Lecture and tutorial will switch time slots in week 04/19 (see below).
  • There will be no lecture on Tuesday the 15.01.19 due to the Tag der Lehre.
  • The tutorials start in week 42, i.e. the first tutorial will be on 16.10.2018. Please bring your Laptop, or similar device, to the first tutorial.

Dates and Ti­mes

Lecture

  • Friday, 8-11 in F0.530

Tutorial

  • Tuesday, 14-16 in F0.530

Exceptions

There are three exceptions to the schedule. The lecture and tutorial switch in weeks 44, 45, and 04/19. I.e. there will be

  • a lecture on Tuesday, 30.10.18, 14-16 with a tutorial on Friday, 02.11.18, 9-11
  • a lecture on Tuesday, 06.11.18, 14-16 with a tutorial on Friday, 09.11.18, 9-11
  • (a lecture on Tuesday, 15.01.19, 14-16 [Lecture cancelled due to Tag der Lehre] with a tutorial on Friday, 18.01.19, 9-11)
  • a lecture on Tuesday, 22.01.19, 14-16 (with a tutorial on Friday, 25.01.19, 9-11 [Tutorial cancelled])

Material

You can find the material related to this lecture (that is slides, in-class exercises, and homework) on jupyter using your IMT account. Logins are synced from PAUL. Please contact us if you are having problem accessing jupyter.

Homework exercises appear every Friday and you have to hand in your solutions by sunday after the respective next. Solutions may be handed in with groups of up to two people. 

Essays

You can also attain homework points by handing in an essay once during the semester. We will offer essay topics only as requested. If you are interested in writing an essay please contact us at the tutorial. After we agreed on a topic, you will have two weeks to hand in your essay. An essay has a point equivalent of roughly two homework sheets, but does not count towards the maximum number of homework points. That means, you can attain 100% of the points without handing in an essay.

Ex­am

There will be oral exams. Details on the exam period TBA.

Exam requirements

You are required to attain at least 50% of all possible homework points in order to participate in the exam.

Exam bonus steps

You can gain up to two bonus grade steps (e.g., improve your grade from 2,3 to 1,7). The bonus only applies if you pass the exam. You gain one step by attaining at least 60% of all possible homework points, and a second step by attaining at least 80% of all possible homework points.

Mo­du­le In­for­ma­ti­on

Lecture: L.079.05512

Lecturer: Prof. Dr. Johannes Blömer

For detailed information please consult the Module Handbook.

Li­te­ra­ture

[1] Michael R. Garey ; David S. Johnson: Computers and intractability: A Guide to the Theory of NP-Completeness. New York: Freeman, ISBN 0-7167-1044-7, 0-7167-1045-5

[2] Michael Sipser: Introduction to the Theory of Computation. 3. ed., Boston, MA.: Cengage Learning, ISBN 1-133-18779-X, 978-1-133-18779-0

[3] Sanjeev Arora ; Boaz Barak: Computational Complexity: A Modern Approach. New York: Cambridge University Press, ISBN 0-521-42426-7

[4] Oded Goldreich: Computational Complexity. Cambridge [u.a.]: Cambridge Univ. Press, ISBN 978-0-521-88473-0

[5] Christos H. Papadimitriou: Computational Complexity. Reading, Mass. [u.a.]: Addison Wesley, ISBN 0-02-015308-2, 0-201-53082-1

[6] Ingo Wegener: Komplexitätstheorie. Berlin [u.a.]: Springer, ISBN 3-540-00161-1

[7] Marcus Schaefer and Christopher Umans: Completeness in the Polynomial-Time Hierarchy: A Compendium. SIGACT News.