
Michael Soltys. An introduction to computational complexity [Click here for a sample] 2009 Published by the Jagiellonian University Press. 
Announcements:
Assignments and Exam:
Name  First Presentation  Second Presentation 
Neerja Pophli  A new approach to nonrepetitive sequences on Sept 25  Unshuffling a Square is NPHard as the 2nd presentation, on November 27th 
Yasmine Sharoda  A short proof of the pigeonhole principle using resolution, on Oct 2  Are there hard examples for Frege systems, on Nov 20 
Robert Fuller  Cook's paper on P vs NP, on Oct 16  Propositional proof complexity: Past, present, and future by Beame and Pitassi on December 4 
Simon Broadhead  The Status of the P versus NP Problem by Fortnow, on Oct 16  On the hardness of graph isomorphism by Jacobo Toran on December 11 
Dhruv Gairola  F. Borneman, PRIMES is in P: A breakthrough for "Everyman" on October 23  A theory of the learnable by L.G. Valiant, on November 13 
Raazia Shafqat  Boolean Satisfiability, on October 2  Probabilistically Checkable Proofs by Madhu Sudan, on December 4 
Mohammed Alabbad  The History and Status of the P versus NP Question by Michael Sipser, on Oct 16  Section 5 of The complexity of propositional proofs by Alasdair Urquhart, on December 4 
Zhipeng Hu  Kolmogorov Complexity on Oct 2  Propositional Proof Complexity: An Introduction by Sam Buss, on Nov 20 
Musa Alhassy  A constructive proof of the general Lovasz Local Lemma by Moser and Tardos on Nov 20  IP=PSPACE, Chapter 11, section 3, in the textbook. This is an important result about protocols, and a good introduction to cryptography; December 4 