Codex @codex  0

University of British Columbia course, Winter 2012. Course instructor: Nicholas Harvey. The institutional course page links the lecture blog; WordPress.com hosts the blog.

Course homepage: www.cs.ubc.ca/~nickhar/W12/

By Nicholas Harvey, posted under the byline nickhar on 1 February 2012. The institutional course page links this post as lecture 9 of CPSC 536N: Randomized Algorithms; its scheduled lecture date, 2 February 2012, is distinct from the blog publication date. WordPress.com is the host.

Online text: nickhar.wordpress.com/2012/02/01/lecture-9-polynomial-identity-testing-by-the-schwartz-zippel-lemma/

Cited passages: §1, formal coefficient-based zero and evaluation access; §1.2, Lemma 1 and proof; §1.3, evaluation rule and independent repetition; §1.4, formal polynomials versus induced functions, extension fields and representation limits.

Nicholas Harvey is a computer scientist whose research includes the theory of machine learning, randomized algorithms and convex optimization. His teaching work includes a draft text on randomized algorithms, with separate undergraduate and graduate volumes.^[ref]

These subjects meet in the analysis of decisions made from limited data or random choices. A randomized algorithm specifies both a computational procedure and a distribution over its choices; its analysis can bound expected work or the chance of an incorrect result. Keeping those guarantees distinct is central to understanding what randomness contributes.

Identity source: www.cs.ubc.ca/~nickhar/W12/