A typo in a book that cost me a day

I have been insatiably reading the computational complexity book by Sanjeev Arora and Boaz Barak, which from the table of contents and review from big guns like Avi Wigderson, Mike Sisper, seems like the holy bible and culmination of all complexity research over the past 3 decades, despite being called a beginning graduate textbook. Eventually I decided to skip ahead to chapter 19 on error correcting code and hardness amplification, but got seriously stumbled by the description of Berlekamp-Welch algoithm (a name I cannot remember without the mnemonic resemblance to “Berkeley campus”). It turns out the author wrote 2d and d instead of 2d + d/2 and d + d/2 for the degrees of the univariate polynomials in the bivariate graph interpolating polynomials; I have been scratching my head trying to understand how one could solve a linear system of 4d equations with 3d + 2 unknowns. But thanks to this wonderful lecture notes by MIT , I was able to reconstruct the correct parameters. Another thing I wish the book had was in-line reference to papers/books where the proofs/algorithms were taken from, but I understand that’s a pretty time-consuming task as well.


About aquazorcarson

math PhD at Stanford, studying probability
This entry was posted in Uncategorized. Bookmark the permalink.

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s