Posted by: atri | February 19, 2010

## Lecture 16: A Geometric Lemma

In today’s lecture we finished the proof of the last piece in the proof of the Plotkin bound: a geometric lemma that bound the number of vectors over a real space that are pairwise at  obtuse angles. This material is from Lecture 17 from fall 2007.

We also covered the notion of explicit codes (where a succinct representation of the code can be computed in time $\mathrm{poly}(n)$ and strongly explicit (linear) code (where each entry of the generator/parity check matrix can be computed in $O(\log{n})$ space).