Structured Models of Computation

Structured Models of Computation

Lecture #20: Lower Bounds for Structured Models of Computation — Decision Trees, and Information-Theoretic and Adversarial Lower Bounds

• Lecture Notes
• Exercise

Lecture #21: Boolean Decision Trees

• Lecture Notes
• Supplemental Material
• Exercise

Lecture #22: Communication Complexity

• Lecture Notes
• Supplemental Material
• Exercise

Lecture #23: Algebraic Computation

• Lecture Notes
• Supplemental Material
• Exercise

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