Acknowledgments

No matter how this thesis is attributed, its contents are actually the fortunate product of a concerted effort by a large, multi-national team of mentors over a twenty-six year period. Often their work involved significant personal sacrifice and little material reward. Though I can acknowledge but a fraction of the members of this team, I am indebted to them all.

First, I would like to thank the computer science department and the communication group at the University of Illinois for their support and environment. In addition, the Computational Science and Engineering program provided the computational power for many of the simulation results in this thesis. Drawn from these groups, my thesis committee provided invaluable advice and suggestions throughout this protracted process, and I would like to individually thank Professors Bruce Hajek, Leonard Pitt, Edward Reingold, and Alexander Vardy.

I was particularly fortunate to have as advisors Professors Alexander Vardy and Edward Reingold. Professor Vardy is clearly a master of his craft and I have benefited tremendously from observing him and conducting research with him. Just as importantly, he permitted me the flexibility of a post-doctorate student in choosing and pursuing research ideas from his ever-abundant list of suggested problems. Professor Reingold also served as a true mentor by providing knowledgeable advise on all aspects of academic life. He expertly oiled bureaucratic wheels, when necessary, and patiently listened and supported the research in this thesis.

I would also like to thank my co-authors, which included Professor Vardy, Professor Tuvi Etzion from the Technion, and Yaron Minsky from Cornell University. In addition, G. David Forney, Jr. and Frank Kschischang provided me with inspiration and background for the lexicode chapter of this thesis, and Jeff Erickson, Amir Khandani, and Ralf Kötter provided stimulating discussions for the Tanner graph chapter of this thesis.

I also benefited greatly from my many colleagues here at the University of Illinois. Dakshi Agrawal served as my model, being half a year ahead of me; Bill Weeks and Weishi Feng served as my encyclopedic references; and Tanya Berger-Wolf, Mitch Harris, Shripad Thite, and Greg Harfst were my sounding boards for new ideas.

Needless to say, this entire exercise would be at most a dream were it not for my loving family. To my parents, Lazar and Tania Trachtenberg, education has been as important as food in my development, and my father has diligently provided critical feedback during the writing of this work. My two sisters, Dalia and Danna, have provided invaluable emotional support, as have my extended family Ted, Adriane, and Scott Moss.

Finally, I dearly thank my wife Felicia, whose love and caring made this entire endeavor worthwhile.