University of California, San Diego

La Jolla, CA 92093-0114

**Office:** 4248 Computer Science Building, EBU3b

**Phone:** (858) 534-1332;` ` **Fax:**
(858) 534-7029;` `

**Email: ** russell@cs.ucsd.edu

**Class Times:MWF, 3-4, WLH 2204**

**TA**: Jiawei Gao

**Russell's Office Hours:** TTh, 3-4.
4248 CSE, or 4258 if it is crowded

**Jiawei's Office Hours:** M, W: 12-1. (tentative, TBA)
**Kenneth's Office Hours:** T, Th: 12-1. (tentative, TBA)

Announcements:

Course Handouts

- 1 tape vs multi-tape TMs.
- RAMs and circuits
- Simulating TMs by circuits
- Diagonalization
- Reductions
- Undecideability of tiling problems
- The class NP
- NP-completeness
- Lecture Notes: Search vs. Decision, and NP-Completeness of Circuit SAT (A bit redundant)
- NP-complete problems (I)
- NP-complete problems (II)
- Coping with NP-completeness, Polynomial hierarchy
- Chris's fanciful presentation (with more technical details) of the consequences of $P=NP$ to informal problems
- Polynomial hierarchy
- Space complexity
- >Space complexity: NL=co-NL
- Randomized algorithms and Probabilistic proofs (pdf)
- Probabilistic Algorithms: polynomial identity testing
- Probabilistic Algorithms: BPP

- Slides from class: TBA