Printer-friendly version

CSci 5403: Complexity Theory

• Understand the fundamental results and problems in complexity theory
  
• Read and understand current research papers in complexity theory and related research areas such as theoretical cryptography, approximation algorithms, and computational learning theory.
• Apply complexity-theoretic tools and results in their own research.
  

• Time and Space complexity.  These are the basic notions from chapters 1-5 of the textbook, which are typically covered to some extent by undergraduate courses. Concepts include TIME(f(n)), SPACE(f(n)), nondeterminism, co-nondeterminism, reductions and completeness.  The main results include the time and Space heirarchy theorems, P vs NP, PSPACE = NPSPACE, NL=coNL and the characterization of the Polynomial time heirarchy.
  
• Circuit complexity.  In complexity theory, circuits are often used to reason about computation because they avoid issues like iteration and self-reference that are introduced by algorithms.  Concepts and results will include circuits as nonuniform computation, the class P/poly, and the relationship between P/poly and the polynomial time heirarchy.
• Randomized algorithms. For some problems, the "best" way we know to solve the problem is with an algorithm  that uses random inputs.  We'll see several examples of randomized algorithms and techniques and study randomized complexity classes, and their relationship to nondeterminism and nonuniformity.  Later, we'll also study derandomization, in which we use computational intractability assumptions to make randomized algorithms into deterministic ones, and explore the relationship between the power of randomness and the existence of intractable problems.
• Counting problems.  Many of the problems we study in undergraduate theory classes are decision or search problems: for a given instance, we either ask whether a solution exists or search for the solution.  We'll study the complexity of counting problems: given an instance, how many solutions does it have?  Concepts and results will include the classes PP, #P, parity-P; the complexity of computing the permanent; Toda's Theorem and the Valiant-Vazirani Theorem.
• Cryptography.  One positive consequence of the apparent limitations of resource-bounded computation is the possibility of cryptography.  Concepts and results include the connection between one-way functions and pseudorandom generators; pseudorandom functions, and encryption.
  
• Proofs and complexity.  One characterization of the P vs NP problem is as the question: "if a language has short proofs, can we find them efficiently?"  Here we will investigate how other notions of proofs, such as interactive, or probabilistically checkable, proofs are related to problem complexity.  Results include Shamir's proof that IP=PSPACE;  Dinur's proof that NP = PCP(log n, O(1)), which means that every NP-language has proofs that can be checked by looking at only a constant number of bits; and the inapproximability of NP problems like MAXSAT and Independent Set.
  

• 14 Homeworks (40%): we will have weekly homeworks, to be turned in at the beginning of class each Tuesday.  Homeworks will consist of (on average) 4 problems, posted on the class website.  Students may choose to work in groups with up to 3 members on homework problems: in this case, you should turn in a single solution with the names of all group members.
  
  Solutions to each homework problem should be on a separate sheet of paper to allow space for feedback. Remember to include your name(s) on each page. It is required that your solutions be typeset electronically, using LaTeX or one of its WYSIWYG variants.  An excellent introduction to latex is the Not-So-Short Guide to LaTeX.  The AMS has a useful Short Math Guide to LaTeX as well.
  
  Each week, two randomly selected problems will be graded on a 4-point scale as follows:
  
  

  4 Points	The solution belongs in the textbook: it has no errors.
  3 Points	The solution has only minor errors: e.g. it is not clearly written or is missing a minor point.
  2 Points	The solution has the "right idea" but has one or more important gaps
  1 Points	The solution does not demonstrate a significant understanding of the problem.
  0 Points	No solution was attempted

  
  
  Students should be aware that solving the homeworks is the minimal work involved to make sure you understand the course; if you have trouble with these problems, you should try more until you are sure you understand the material.
  
  Due dates for all assignments are strict: all homeworks must be received at the very start of the class in which they are due in order to receive full credit. Late homeworks turned in before 3pm on Wednesday will be considered for 50% credit, and after 3pm on the day after it is due, a homework is worth 0 points, with no exceptions. 
  
  Keep a copy of each of your submissions as evidence that you have indeed submitted each assignment. Do not ever put your assignment under the instructor's office door: this is a certain way to receive zero points for an assignment.
  
  
• 5 Take-Home Exams (40%).  Roughly every three weeks, a "take-home" exam question will be posted to the class website at noon on a Monday or Wednesday.  Students are to turn in their exams (electronically typeset) by the end of lecture the following day.  The dates of these exams are posted on the class schedule. No late take-home solutions will be accepted.  Exams will be graded on a 10-point scale, and each student's worst question score will be dropped.
  

• 4 Example Solutions (20%):  Each student will be assigned to write complete example solutions to four homework problems distributed throughout the semester.   Your example solutions should be more complete than regular solutions, explaining all of the "details" of the solution and why the solution is correct.  I will typically require some revisions to your solutions before they are posted; you will be considered to have satisfied this requirement (earned 20%) if all of your assigned solutions are eventually accepted and at least three of your assigned solutions are posted within one week of the original due date.