 CMPT 710 - Complexity Theory: Lecture 18

By Valentine Kabanets, explicitly credited on PDF p. 1. Authored lecture notes within CMPT 710 and CMPT 407 - Computational Complexity - Fall 2007, dated 8 November 2007. Simon Fraser University hosts the notes; the instructor credit is separate from the lecture byline.

Online text: www2.cs.sfu.ca/~kabanets/710_2007/new_lectures/l18.pdf

Cited passages: §3.1, printed pp. 3–4, Lemma 4, hypotheses and inductive proof; §3.2, printed p. 4, formula equality, one-sided error and degree/bit-cost discussion.