Instructor: Pooya Hatami (last_name.2@osu.edu)
Grader info: TBA
Lectures:
 TuesdayThursday 14:20 – 15:40
 Zoom Info can be found on Carmen
 Lectures will be live on zoom (the recording will also be made available on Carmen).
 In some occasions we may have prerecorded (not live) lectures posted on Carmen. Make sure to check your emails for such announcements.
Office Hours:
Pooya Hatami: Thursdays 4:00pm5:30pm (Zoom info on Carmen)
Lecture Notes (click here)
Above I will maintain a pdf of the notes of the covered material.
Homework Assignments
There will be four homeworksets which will be posted on Carmen and solutions should be posted as a pdf file on Carmen. The homework will be graded based on correctness rather than effort alone.
Course Summary (tentative):
 This course intends to introduce the student to theory of computability, and computational complexity theory, with more emphasis on the latter.
 Computability Theory: Notions of algorithms, Turing Machines (deterministic, nondeterministic, …), ChurchTuring Thesis, Decidability, Turingrecognizability and Enumerability, Diagonilization, Reductions
 Complexity Theory: Complexity classes and measures, P, NP, coNP, NPcompleteness, Hierarchy Theorems, Space Complexity, Boolean circuits, randomized computation, RP, ZPP, BPP, RL, BPL
Suggested Reading:

 Sanjeev Arora and Boaz Barak, Complexity Theory: a Modern Approach
 Michael Sipser, Introduction to the Theory of Computation
The OSU Bookstore link for both books: https://tinyurl.com/W21CSE632134455
Grading: The grades will be based on 4 homeworkassignments and one takehome final exam. There will be no midterm or final exams.
76% Homeworks + 24% Final Exam.
Prerequisites:
CSE 3321/5321 “Automata and Formal Languages” (625) or equivalent or consent of instructor. Automata theory, mathematical background/maturity (Chapter 0 of Sipser’s book: mathematical proof, by contradiction, by induction, sets, relations, functions, cardinality).
This is a rigorous course with an emphasis on mathematical proofs. We assume familiarity with reading, writing, and coming up with formal mathematical proofs.
Policy on Collaboration:
Studying in groups is encouraged, however we encourage you to work on the homeworkassignments on your own. If you do collaborate, state it clearly at the beginning of your solution (give name of collaborator for each problem, even if you were the one helping someone.). Acknowledged collaboration does not mean copying someone else’s solution: Discuss ideas not the final solutions, use the ideas to solve the problems yourself and then write your own rendering.