Randomization, Interaction, and Approximation

Randomization, Interaction, and Approximation

Lecture #17: Randomized Computation

• Lecture Notes
• Supplemental Material
• Exercise

Lecture #18: Interactive Proofs

• Lecture Notes
• Supplemental Material
• Exercise

Lecture #19: Approximation Algorithms, the PCP Theorem, and the Hardness of Approximation

• Lecture Notes
• Supplemental Material
• Exercise

Assignment #4: Randomized Computation

• Problems To Be Solved

cpsc 511/611 computer science faculty of science u of c

CPSC 511/611 intro to course deterministic computation nondeterministic computation space-bounded computation circuit computations randomzation, interaction and approximation structured models other topics assignments tests