CSE 5329: Advanced Complexity Theory (Au21)

Instructor:  Pooya Hatami (last_name.2@osu.edu) 


There is no weekly office hours. Zoom meetings with the instructor can be scheduled via email. 


Lecture Notes (Updated on Nov 4)

COVID-related guidelines:


This is a seminar-type course, and each student will be asked to present a minimum of 1 of the lectures, as well as help in proof-reading and editing of the lecture notes for a few of the lectures. 

We will have exercises and problems at the end of different sections of the notes, however, these need not be submitted and will not contribute to your grade. You are encouraged to work on these problems, and reach out to the instructor if you need to discuss them further. 

There is no final exam or projects for this course.  

Course Summary (tentative):

  • This course can be thought of as a continuation of and builds on CSE 3321 and CSE 6321. We intend to cover topics in complexity theory such as: role of randomness in time and space complexity (RP, BPP, RL, BPL), proof barriers to the well-known P vs NP problem, non-uniform models of computation such as bounded depth circuits (P/poly, TC, AC, NC, ACC), multi and two-party communication complexity, interactive proofs, circuit lower-bounds, derandomization, arithmetic circuits, branching programs, hardness amplification, hardness vs randomness, interactive proofs, quantum computing, and query complexity and analysis of Boolean functions.

 Sources (links to the relevant sources will be added below): 

You must be familiar with the topics and concepts introduced in
CSE 6321 “Complexity and Computability”. A link to the instructor’s lecture notes for CSE 6321 is provided in “Sources” section.