Introduction to logic and proof techniques, formal languages, automata theory, and computational complexity. Specific topics include regular and context-free languages, Turing machines, NP-completeness, and undecidability.
This class is a traditional introduction to the Theory of Computation with an introduction to Zero-Knowledge proofs used in cryptographic protocols. Specific topics include regular and context-free languages, Turing machines, NP-completeness, Hierarchies, randomness, cryptography, Interactive (Zero Knowledge) proof systems.
|
Text Book: |
Computational Complexity- A Modern Approach by Arora and Barak (ISBN 978-0-521-42426-4) |
|
|
Class Time: |
Monday 4.30-7.20 pm |
|
|
Class Room: |
Robinson Hall, Room B 104 |
|
|
Instructor: |
Duminda Wijesekera (dwijesek AT gmu DOT edu), 703-993-5030 or 703-993-1578 |
|
|
Office Hours: |
Research Hall 436, M, W 7.30-8.30 or by appointment |
|
|
TA: |
Xin Guan (xguan AT masonlive DOT gmu DOT edu |
|
|
TA Office Hours: |
Tuesday 8-10 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 |
Context-free 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 |
P-time reductions |
2 |
|
|
March 03 |
Mid-term 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 Catch-up |
|
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. |