Introduction to logic and proof techniques, formal languages, automata theory, and computational complexity. Specific topics include regular and contextfree languages, Turing machines, NPcompleteness, and undecidability.
This class is a traditional introduction to the Theory of Computation with an introduction to ZeroKnowledge proofs used in cryptographic protocols. Specific topics include regular and contextfree languages, Turing machines, NPcompleteness, Hierarchies, randomness, cryptography, Interactive (Zero Knowledge) proof systems.
Text Book: 
Computational Complexity A Modern Approach by Arora and Barak (ISBN 9780521424264) 

Class Time: 
Monday 4.307.20 pm 

Class Room: 
Robinson Hall, Room B 104 

Instructor: 
Duminda Wijesekera (dwijesek AT gmu DOT edu), 7039935030 or 7039931578 

Office Hours: 
Research Hall 436, M, W 7.308.30 or by appointment 

TA: 
Xin Guan (xguan AT masonlive DOT gmu DOT edu 

TA Office Hours: 
Tuesday 810 pm 

Prerequisites: 
CS 583 (Algorithms) and discrete mathematics. 

Grading: 
Homework=40%, Midterm=30%, Final=30% 

3
Date 
Topic 
Book Chapter 
HW / Exam 
Jan 27 
Regular languages 
In Blackboard 

Feb 03 
Contextfree languages 
In Blackboard 
HW 1 out 
Feb 10 
Turing machines 
0, 1 

Feb 17 
Complexity Classes, P, NP 
2 
HW 1 in HW 2 out 
Feb 24 
Ptime reductions 
2 

March 03 
Midterm Exam 
2 
HW 2 in HW 3 out 
March 10 
Spring Break 
In Class 

March 17 
Diagonalization 


March 24 
Space Complexity 
4 
Returen Midterm Exam 
March 31 
The Polynomial Hierarchy 
5 
HW 3 in, HW 4 out 
April 07 
The Polynomial Hierarchy 
5 

April 14 
Randomized Computations 
7 
HW 4 in HW 5 out 
April 21 
Intercative Proofs 
8 

April 28 
Cryptography 
9 
HW 5 in HW 6 out 
May 05 
Review and Catchup 

HW 6 in 
May 14 
Final Exam 
S 

Homework: 
All homework solutions must be done individually. Written submissions should be handed lover to the TA, either through the Blackboard, email or mailbox. 
Note on Exams: 
In Class, closed book, closed neighbor, no electronics during exams. 
Proofs: 
I expect proofs to be written symbolically acceptable at the level of a graduate theory class. English descriptions, essays or alternate explanations are NOT substitutes for proofs. 
Partial Credit: 
Partial credit is given for incomplete proofs or counterexamples ONLY IF they can be completed as begun. 
Honor Code: 
GMU honor code applies to all submitted work for this course. 