Finucane, HilaryMitzenmacher, Michael2015-11-202009Finucane, Hilary and Michael Mitzenmacher. 2009. Worst-Case and Average-Case Floating Codes for Flash Memory. Harvard Computer Science Group Technical Report TR-04-09.http://nrs.harvard.edu/urn-3:HUL.InstRepos:23597704Flash memory is used in portable electronic devices like cell phones, mp3 players, digital cameras, and PDAs. The question of how to code information in flash memory is a difficult one whose answer can have effects on the speed and lifespan of a chip of flash memory. The main factor to be taken into account when designing codes for flash memory is the difference in cost between decreasing and increasing the state of a cell; decreasing the state of a cell requires first the resetting of an entire section of cells. Codes that focus on maximizing the number of updates between these reset operations are called floating codes. Worst-case floating codes focus on maximizing the lower bound on the number of updates between resets, and average-case floating codes focus on maximizing the average number of updates between resets. In this thesis, we review the work done on both worst-case and average-case floating codes. We also introduce a new code which performs as well as the previous best worst-case floating code but is significantly simpler, and a second code which performs asymptotically better.en-USResearch Paper or Report2015-11-20