# Harvard Theory of Computation Seminar

### Zhenming Liu, Harvard

Place and Time: Monday, Feb 23, 2009, Piece Hall 320

Refreshments at 2:30pm, talk at 2:45

### ABSTRACT

Floating codes are codes designed to store multiple values in a Write Asymmetric Memory, with applications to flash memory. In this model, a memory consists of a block of $n$ cells, with each cell in one of $q$ states $\{0,1,\ldots,q-1\}$. The cells are used to represent $k$ variable values from an $\ell$-ary alphabet. Cells can move from lower values to higher values easily, but moving any cell from a higher value to a lower value requires first resetting the entire block to an all 0 state. Reset operations are to be avoided; generally a block can only experience a large but finite number of resets before wearing out entirely. A code here corresponds to mapping from cell states to variable values, and a transition function that gives how to rewrite cell states when a variable is changed.

Previous work has focused on developing codes that maximize the worst-case number of variable changes, or equivalently cell rewrites, that can be experienced before resetting. In our work, we introduce the problem of maximizing the {\em expected} number of variable changes before resetting, given an underlying Markov chain that models variable changes. We demonstrate that codes designed for expected performance can differ substantially from optimal worst-case codes, and suggest constructions for some simple cases.

This is a joint work with Flavio Chierichetti, Hilary Finucane, and Michael Mitzenmacher