This dissertation studies problems of data management under unreliable conditions: how can data be efficiently reconstructed, synchronized, transmitted, and stored in the presence of uncertainty or noise? The common underlying thread running through the approaches to these problems is the discipline of coding theory.

Problems related to data editing and modification are considered in the first part of the dissertation. For the combinatorial data reconstruction problem, a new result regarding the minimum number of traces needed for exact reconstruction is introduced, resolving an open problem. Several applications and examples are discussed. An efficient and practical protocol relying on building blocks from coding theory is proposed for synchronizing data with general, non-uniform edits; this protocol outperforms existing tools in many scenarios. In addition, synchronization of data represented by complete or partial ranked lists is studied and novel bounds and code constructions are presented.

The second part of the dissertation is concerned with problems of efficient and robust data storage. Inspired by memories operating in high-radiation environments, an exploration of non-uniform noisy decoding for the popular low-density parity-check (LDPC) class of error-correcting codes is performed. A novel model and density evolution analysis are introduced. The problem of comparing, representing, and classifying practical error-control strategies for caches and other on-chip memories is tackled by introducing a powerful explanatory theoretical framework. Finally, a novel coding problem for data used in learning algorithms is considered.

The insights from this work, combining tools from a variety of disciplines, including algorithms, coding and information theory, and combinatorics, contribute to a unified approach to general problems of data. Given the ongoing data revolution, solutions to these problems are of paramount importance.

Non-volatile memories (NVMs) are the most important modern data storage technology. Despite their significant advantages, NVMs suffer from poor reliability due to issues such as voltage drift over time, overwriting, and inter-cell coupling. This thesis applies coding-theoretic techniques to NVMs in order to improve their reliability and extend their lifetimes. In particular, we focus on two classes of problems: those related to the use of thresholds to read memory cells, and those related to inter-cell coupling in the data representation scheme known as rank modulation.

The first part of the thesis develops the concept of dynamic thresholds. In NVMs, reading stored data is typically done by comparing cell values against a set of predetermined, fixed threshold references. However, due to common NVM problems, fixed threshold usage often results in significant asymmetric errors. To combat these problems, the notion of dynamic thresholds was recently introduced. Such thresholds are allowed to change in order to react to changes in cell value distributions. Thus far, dynamic thresholds have been applied to the reading of binary sequences in memories with single-level cells (SLCs).

In this work, the use of dynamic thresholds for multi-level cell (MLC) memories is explored. A general scheme to compute and apply dynamic thresholds is provided. We derive a series of performance results, based on both practical considerations and theoretical analysis. We show that the proposed threshold scheme compares favorably with the best-possible threshold scheme. Finally, we develop error-correcting codes that are tailored to take advantage of the properties of dynamic thresholds. Code constructions are provided for different channel models, including those allowing limited and unlimited numbers of errors of varying magnitude limitations.

The second part of this thesis is focused on the application of constrained coding to rank modulation. Rank modulation is an MLC NVM scheme where information is represented by the rankings of charge levels in an entire block of cells, rather than the absolute charge level of any particular cell. This scheme resolves certain NVM problems, including write-asymmetry, as it allows for a transition from any information state to any other solely through the addition of charge to an appropriate subset of cells. However, the scheme still suffers from inter-cell coupling errors. Such errors are due to inadvertent charge level increases in cells whose neighboring cells have significantly larger levels.

We introduce constraints that mitigate the inter-cell coupling problem in rank modulation. These constraints typically limit the differences between the ranks of neighboring elements in a permutation, and thus limit the charge level differences between adjacent cells, reducing inter-cell coupling effects. In particular, we analyze the single neighbor k-constraint, where neighboring cells' ranks cannot differ by more than k. We provide the best-known bounds for the sizes of sets meeting this constraint, and, for certain cases where the parameter k involves a constant term, we derive exact expressions. We perform an asymptotic analysis. Lastly, we introduce an efficient scheme that allows us to systematically generate constrained permutations.