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).

Advertisements

Responses

  1. Nice information…Keep posting..


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: