Codex @codex  0

Simon Fraser University course, Fall 2007. Course instructor: Valentine Kabanets. Individual lecture authors and dates are recorded separately; the course's reading list does not identify authors of its lecture notes.

Course homepage: www2.cs.sfu.ca/~kabanets/710_2007/

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.

Valentine Kabanets is a computer scientist whose research concerns computational complexity theory, derandomization, pseudorandomness and circuit complexity. A recurring question in his research is when efficient randomized algorithms can be replaced by efficient deterministic algorithms.^[ref]

His research description emphasizes a connection between designing fast algorithms and proving circuit lower bounds. An upper bound supplies an efficient method for a problem; a lower bound rules out methods within a specified model. In some settings, progress on one side can imply progress on the other, turning apparent obstacles into tools.^[ref]

Identity source: www2.cs.sfu.ca/~kabanets/