CS 151: Complexity Theory (Spring 2004)

Instructor: Chris Umans

Office: Jorgensen 286

Times: Tu/Th 10:30-12:00 in 125 Steele

TA: David Soloveichik

Office hours:

• Tuesdays 1-2 in Jorgensen 286, and by appointment (Chris)
• Wednesdays 5-6 in Moore 204 (David)

Announcements:

• I have packets of graded material and final grades available for pick-up. Have a great summer!
• On problem 4 of the midterm, the hint should refer to problem 3 of Problem Set 3 rather than problem 4.
• The third problem of Problem Set 4 is optional. You may solve it for extra credit.

Handouts:

Lecture Slides:

• Lecture 1: languages, complexity classes, Turing Machines, reductions and completeness (ppt, pdf)
• Lecture 2: time and space classes, hierarchy theorems, relationships between classes, P- + EXP-complete problems (ppt, pdf)
• Lecture 3: nondeterminism, NTIME hierarchy theorem, Ladner's Theorem (ppt, pdf)
• Lecture 4: sparse languages and NP, nondeterministic space classes, s-t-connectivity, Savitch's Theorem, I-S Theorem (ppt, pdf)
• Lecture 5: circuits, uniformity and advice, NC hierarchy, formula lower bound on the Andreev function (ppt, pdf)
• Lecture 6: Razborov's lower bound on monotone circuits for CLIQUE (ppt, pdf)
• Lecture 7: communication complexity, Schwartz-Zippel Lemma, Valiant-Vazirani Theorem, randomized complexity classes, Adelman's Theorem (ppt, pdf)
• Lecture 8: pseudo-random generators and derandomization, Goldreich-Levin hard bit, Yao's Lemma, BMY generator (ppt, pdf)
• Lecture 9: Nisan-Wigderson pseudo-random generator, error-correcting codes from polynomials (ppt, pdf)
• Lecture 10: Decoding Reed-Muller codes, transforming worst-case hardness into average-case hardness, extractors (ppt, pdf)
• Lecture 11: Trevisan Extractor, strong error reduction for BPP, RL, the Polynomial-Time Hierarchy (ppt, pdf)
• Lecture 12: the Polynomial-Time Hierarchy, complete problems for levels of PH and PSPACE (ppt, pdf)
• Lecture 13: natural complete problems for levels of PH and PSPACE, interactive proofs, graph nonisomorphism (ppt, pdf)
• Lecture 14: Karp-Lipton Theorem, BPP in PH, the power of IP (ppt, pdf)
• Lecture 15: IP=PSPACE, Arthur-Merlin Games, AM and MA, approximation algorithms (ppt, pdf)
• Lecture 16: gap-producing and gap-preserving reductions, Probabilistically Checkable Proofs, elements of the proof of the PCP Theorem (ppt, pdf)
• Lecture 17: #P, relativization, natural proofs, course summary (ppt, pdf)

Problem Sets:
{"ft_lang_label":"__label__en","ft_lang_prob":0.7030263,"math_prob":0.80538994,"size":2978,"snap":"2020-10-2020-16","text_gpt3_token_len":858,"char_repetition_ratio":0.22225958,"word_repetition_ratio":0.08830022,"special_character_ratio":0.26460713,"punctuation_ratio":0.21354167,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.96194434,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-04-05T07:43:22Z\",\"WARC-Record-ID\":\"<urn:uuid:c51431e8-afa8-4e6d-8ed5-af3128ebaea7>\",\"Content-Length\":\"5849\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:25bc731f-a68d-4f5c-96d6-79c6f7fd0ae8>\",\"WARC-Concurrent-To\":\"<urn:uuid:2a23d642-0b22-403d-9f9a-4e88456e7f1b>\",\"WARC-IP-Address\":\"131.215.140.19\",\"WARC-Target-URI\":\"http://users.cms.caltech.edu/~umans/cs151-sp04/index.html\",\"WARC-Payload-Digest\":\"sha1:3UC4R6MP4OBLZLBA5YH3XSIBICXST44R\",\"WARC-Block-Digest\":\"sha1:CHCSFA5ZKOFJBRWFVCTYJC64Z4FJD35D\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-16/CC-MAIN-2020-16_segments_1585370529375.49_warc_CC-MAIN-20200405053120-20200405083120-00405.warc.gz\"}"}