CMSC 28130 Honors Introduction to Computational Complexity Theory

Winter 2025

Material for the midterm MidTopics.html

Answers for Midterm questions Mid-Answers.pdf Final Study Guide: FinalTopics.html

Solution sketches for Assignment 7 7Sol.pdf

  • Course Mechanics
  • Course Overview
  • What we covered so far
  • What we may cover next class
  • Assignments and Handouts
    •

    Course Mechanics Much information at mechanics.html
    Current plan for grading: homework 35% midterm 30% final 35%

    Instructor

    Janos Simon
    337 Crerar Library
    email: janos (dot) simon (at) gmail (dot) com
    Office hours: Th 4-5 JCL Common Area 3D or by appointment.

    TA

    Tiago Royer

    Office hours

    M 4-5 PM
    JCL Common Area 3A

    Lectures:MWF 2:30-3:20 Ry 177

    Photos of Blackboards

    Some are not very good quality, and they are sketches, not sentences....
    They can be found in directory B, in subdirectories month-day.

    If you need special accommodations, please send me email ASAP. Textbook: M. Sipser: Introduction to the Theory of Computation.
    3rd ed.
    Cenage Learning.

    Other references


    There are PowerPoint slides of the material.
    They do not exactly match the order I am using this quarter, but may be a useful reference.
    They are in directory PP

    Books and papers:

    1. S. Arora and B. Barak: Computational Complexity: A Modern Approach
      Cambridge U Press 2009. The standard txtbook for the graduate version of this course.
    2. O. Goldreich: Computational Complexity--A conceptual perspective.
      Cambridge U Press 2008. A somewhat idiosyncratic text covering the second part of the course
      (and material for a couple more quarters) with good explanations.
    4. A. Wigderson: Mathematics and Computation A Theory Revolutionizing Technology a\ nd Science
      Princeton University Press 2019
      A wonderful book, with nice description of the Computational Complexity, with proo\ f sketches, motivations, and insights.
      A LOT of material, expects a fair amount of Math ability.
    5. A (somewhat sensationalist) account of Radhanath Sikdar: here
    6. Turing's paper: here.
      Turing, A.M. (1936), On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 2 (published 1937), 42 (1), pp. 230-65, doi:10.1112/plms/s2-42.1.230 (and Turing, A.M. (1938), On Computable Numbers, with an Application to the Entscheidungsproblem: A correction, Proceedings of the London Mathematical Society, 2 (published 1937), 43 (6), pp. 544-6, doi:10.1112/plms/s2-43.6.544). (Online version.)
      The Wikipedia entry is also good.
    7. More to be added as the course progresses.
    -

    Please visit the page mechanics.html for information about how the course is going to be taught, how to submit work, office hours, etc. ---->

    Course Overview

    We will try to cover most of Part 2 and 3 of the Sipser book . We will not strictly follow it, and we will not do it in the exact same order.

    Please note that the 2nd and 3rd editions are slightly different. This is important when doing problems from the text.

    This seems to be a relatively small Honors class: we may have the opportunity to do more than the outline below (perhaps a chance for student presentations of more advanced material)

    Approximate Syllabus

    This is an overall plan for the course. I will surely not follow it in every detail. If there is time, we will explore other topics (further topics on randomized computations, quantum computation, average case complexity, ?)

    Material covered so far

    See here

    Read ahead

    Next lecture Material to be covered next: here

    Homework

    1. First Assignment (due 1/15)
    2. Second Assignment (due 1/22)
    3. Third Assignment (due 1/31)
    4. Fourth Assignment (due 2/5)
    5. Fifth Assignment (due 2/17)
    6. Sixth Assignment (due 2/26)
    7. Seventh Assignment (due 2/26)