Project: Random Graphs and Applications to Codes and Cryptography Student Researchers: Laura Elena Serban, Evdokia Nikolova, Mihaela Enachescu Advisor: Michael Mitzenmacher Institution: Harvard University Detection and correction of errors introduced in a channel is vital to reliable communication. In this project, we will focus on designing new small and fast error-correcting codes by building graphs with appropriate properties. Certain error-correcting codes can be pictured as bipartite graphs; the edge connections between nodes correspond to relationships between bits defined by the codes. Most of the existing analysis on error-correcting codes has been asymptotic; it only applies if there are millions of bits. In practical situations, one might want codes for a few hundred or few thousand bits. For example, such small codes may be useful for error-protection schemes on CDs or CD-ROMs. Little work has been done either in analyzing or experimenting with codes of this form of small size. Also, little work has been done in optimizing such codes for raw speed, which may also be important in practical applications. We plan to design and search for good graphs using heuristic search techniques, including possibly hill-climbing and simulated annealing. We hope to improve on previous work by deriving new small and fast codes more effective than those currently known in terms of error-correcting capabilities.