Instructor: Pooya Hatami (firstname.lastname@example.org)
- Time: Thursday 14:15 – 16:05 (IN PERSON)
- Location: Pomerene Hall 150 (Classroom info:https://odee.osu.edu/pomerene-hall-150)
There is no weekly office hours. Zoom meetings with the instructor can be scheduled via email.
Lecture Notes (Updated on Nov 4)
- Mask requirements: https://mediasite.osu.edu/Mediasite/Play/ea7c86234b884a4d9aa74f27798a42ad1d
- University COVID policies: https://safeandhealthy.osu.edu
- University policy on expectations and accountability measures: https://safeandhealthy.osu.edu/accountability
- COVID-related medical accommodation requests should be requested through SLDS: https://safeandhealthy.osu.edu/accommodations
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):
- Sanjeev Arora and Boaz Barak – Complexity Theory: a Modern Approach
- Oded Goldreich – Computational Complexity, A Conceptual Perspective
- Avi Wigderson – Mathematics and Computation
- Ryan O’Donnell – Analysis of Boolean Functions
- Instructor’s notes for CSE 6321
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.