CS190, UCSB, 2010-09/12

Fall 2010 Update

As not enough students enrolled for this course in Fall 2010, CS190 has been cancelled. If you would like to attend this course in the future, please let me (vandam@cs) know which quarter works best for you.

This is the general course site for CS190, "Theoretical Computer Science and Its Applications", by Wim van Dam at UC Santa Barbara.

Unless stated otherwise, this site and all of its content (including slides, homework assignments, midterms and their answer keys) is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License (Wim van Dam, Department of Computer Science and Department of Physics, UC Santa Barbara, 2010)

General Course Information

• Course No.: CS 190
• Course Title: Theoretical Computer Science and Its Applications
• Total Credits: 4 units
• Prerequisites: Approval by instructor (but you should think of this as a follow-up to CS130AB and CS138).
• Registration: To register for a CS190 course an approval code is required. If you want to enroll, please email WvD your grades for CS138, CS130A, and/or 130B, after which he will ask the Undergraduate Program Coordinator (Benji Dunson) for an enrollment code. Thanks.
• Description: In this course we will discuss some classic, but also some more recent, results in theoretical computer science. We will also look at the applications of these results to the world outside of CS. Core topics are: Turing's original thesis and the theory of computability, the modern version of Turing's thesis and feasibility, optimization and NP complete problems, probabilistic algorithms versus the method of derandomization. Optional topics are: average case complexity and cryptography, games and PSPACE completeness, interactive proofs, zero-knowledge proofs, probabilistically checkable proofs, phase transitions in computational problems, quantum algorithms and the most modern version of Turing's thesis.

Core Topics

• Computability: Turing machines, Turing's thesis, halting problem, uncomputable problems, reductions, Hilbert's 10th Problem, more uncomputable problems, Rice's theorem versus program verification
• Feasibility: space, time, practical algorithms, reductions, modern Turing thesis, provably intractable problems
• P vs NP: combinatorial optimization, witnesses, NP-hardness, NP-complete problems, Millennium Problem of the Clay Institute
• Probability: probabilistic algorithms, P vs BPP, even more modern Turing thesis

Optional Topics (depending on interest by students)

• Cryptography: leveraging hardness of problems, public key cryptography, RSA, elliptic curve cryptography, average case complexity
• Beyond NP: polynomial hierarchy, PSPACE, complexity of games, circuit optimization
• Interactive systems: interactive proofs, IP = PSPACE, zero-knowledge proofs, probabilistically checkable proofs
• Phase transitions: average combinatorial problems, SAT threshold
• Quantum computing: computing with a quantum mechanical device, Shor's factoring algorithm, most modern Turing thesis

Themes

• Turing machine model of computation and Turing's thesis: how Turing's model of computation captures the physics of performing computation
• Reductions: how to use algorithms to reduce problems to each other
• Proofs: the different ways of proving things: deterministically, nondeterministically, probabilistically, interactively

Weekly Schedule

• Tuesday, 3:30 - 4:45 pm: Class in LSB 1101
• Thursday, 3:30 - 4:45 pm: Class in LSB 1101