Randomness-efficient curve sampling

Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the sampled curve is still low-degree. This property is often used in combination with the sampling property and has found many applications, including PCP constructions, local decoding of codes, and algebraic PRG constructions.

The randomness complexity of curve samplers is a crucial parameter for its applications. It is known that (non-explicit) curve samplers using O(log N + log(1/δ)) random bits exist, where N is the domain size and δ is the confidence error. The question of explicitly constructing randomness-efficient curve samplers was first raised in [TU06] where they obtained curve samplers with near-optimal randomness complexity.

In this thesis, we present an explicit construction of low-degree curve samplers with optimal randomness complexity (up to a constant factor) that sample curves of degree (m log_q(1/δ))^O(1) in F_q^m. Our construction is a delicate combination of several components, including extractor machinery, limited independence, iterated sampling, and list-recoverable codes.

Macroscopically Dissipative Systems with Underlying Microscopic Dynamics : Properties and Limits of Measurement

While some of the deepest results in nature are those that give explicit bounds between important physical quantities, some of the most intriguing and celebrated of such bounds come from fields where there is still a great deal of disagreement and confusion regarding even the most fundamental aspects of the theories. For example, in quantum mechanics, there is still no complete consensus as to whether the limitations associated with Heisenberg's Uncertainty Principle derive from an inherent randomness in physics, or rather from limitations in the measurement process itself, resulting from phenomena like back action. Likewise, the second law of thermodynamics makes a statement regarding the increase in entropy of closed systems, yet the theory itself has neither a universally-accepted definition of equilibrium, nor an adequate explanation of how a system with underlying microscopically Hamiltonian dynamics (reversible) settles into a fixed distribution.

Motivated by these physical theories, and perhaps their inconsistencies, in this thesis we use dynamical systems theory to investigate how the very simplest of systems, even with no physical constraints, are characterized by bounds that give limits to the ability to make measurements on them. Using an existing interpretation, we start by examining how dissipative systems can be viewed as high-dimensional lossless systems, and how taking this view necessarily implies the existence of a noise process that results from the uncertainty in the initial system state. This fluctuation-dissipation result plays a central role in a measurement model that we examine, in particular describing how noise is inevitably injected into a system during a measurement, noise that can be viewed as originating either from the randomness of the many degrees of freedom of the measurement device, or of the environment. This noise constitutes one component of measurement back action, and ultimately imposes limits on measurement uncertainty. Depending on the assumptions we make about active devices, and their limitations, this back action can be offset to varying degrees via control. It turns out that using active devices to reduce measurement back action leads to estimation problems that have non-zero uncertainty lower bounds, the most interesting of which arise when the observed system is lossless. One such lower bound, a main contribution of this work, can be viewed as a classical version of a Heisenberg uncertainty relation between the system's position and momentum. We finally also revisit the murky question of how macroscopic dissipation appears from lossless dynamics, and propose alternative approaches for framing the question using existing systematic methods of model reduction.

Rewriting Schemes for Flash Memory

Flash memory is a leading storage media with excellent features such as random access and high storage density. However, it also faces significant reliability and endurance challenges. In flash memory, the charge level in the cells can be easily increased, but removing charge requires an expensive erasure operation. In this thesis we study rewriting schemes that enable the data stored in a set of cells to be rewritten by only increasing the charge level in the cells. We consider two types of modulation scheme; a convectional modulation based on the absolute levels of the cells, and a recently-proposed scheme based on the relative cell levels, called rank modulation. The contributions of this thesis to the study of rewriting schemes for rank modulation include the following: we

•propose a new method of rewriting in rank modulation, beyond the previously proposed method of “push-to-the-top”;

•study the limits of rewriting with the newly proposed method, and derive a tight upper bound of 1 bit per cell;

•extend the rank-modulation scheme to support rankings with repetitions, in order to improve the storage density;

•derive a tight upper bound of 2 bits per cell for rewriting in rank modulation with repetitions;

•construct an efficient rewriting scheme that asymptotically approaches the upper bound of 2 bit per cell.

The next part of this thesis studies rewriting schemes for a conventional absolute-levels modulation. The considered model is called “write-once memory” (WOM). We focus on WOM schemes that achieve the capacity of the model. In recent years several capacity-achieving WOM schemes were proposed, based on polar codes and randomness extractors. The contributions of this thesis to the study of WOM scheme include the following: we

•propose a new capacity-achievingWOM scheme based on sparse-graph codes, and show its attractive properties for practical implementation;

•improve the design of polarWOMschemes to remove the reliance on shared randomness and include an error-correction capability.

The last part of the thesis studies the local rank-modulation (LRM) scheme, in which a sliding window going over a sequence of real-valued variables induces a sequence of permutations. The LRM scheme is used to simulate a single conventional multi-level flash cell. The simulated cell is realized by a Gray code traversing all the relative-value states where, physically, the transition between two adjacent states in the Gray code is achieved by using a single “push-to-the-top” operation. The main results of the last part of the thesis are two constructions of Gray codes with asymptotically-optimal rate.

I. Anisotropy and crystal structure of ferromagnetic thin films. II. Investigations into magnetic microstructure by Lorentz microscopy

The induced magnetic uniaxial anisotropy of Ni-Fe alloy films has been shown to be related to the crystal structure of the film. By use of electron diffraction, the crystal structure or vacuum-deposited films was determined over the composition range 5% to 85% Ni, with substrate temperature during deposition at various temperatures in the range 25° to 500° C. The phase diagram determined in this way has boundaries which are in fair agreement with the equilibrium boundaries for bulk material above 400°C. The (α+ ɤ) mixture phase disappears below 100°C.

The measurement of uniaxial anisotropy field for 25% Ni-Fe alloy films deposited at temperatures in the range -80°C to 375°C has been carried out. Comparison of the crystal structure phase diagram with the present data and those published by Wilts indicates that the anisotropy is strongly sensitive to crystal structure. Others have proposed pair ordering as an important source of anisotropy because of an apparent peak in the anisotropy energy at about 50% Ni composition. The present work shows no such peak, and leads to the conclusion that pair ordering cannot be a dominant contributor.

Width of the 180° domain wall in 76% Ni-Fe alloy films as a function of film thickness up to 1800 Å was measured using the defocused mode of Lorentz microscopy. For the thinner films, the measured wall widths are in good agreement with earlier data obtained by Fuchs. For films thicker than 800 Å, the wall width increases with film thickness to about 9000 Å at 1800 Å film thickness. Similar measurements for polycrystalline Co films with thickness from 200 to 1500 Å have been made. The wall width increases from 3000 Å at 400 Å film thickness to about 6000 Å at 1500 Å film thickness. The wall widths for Ni-Fe and Co films are much greater than predicted by present theories. The validity of the classical determination of wall width is discussed, and the comparison of the present data with theoretical results is given.

Finally, an experimental study of ripple by Lorentz microscopy in Ni-Fe alloy films has been carried out. The following should be noted: (1) the only practical way to determine experimentally a meaningful wavelength is to find a well-defined ripple periodicity by visual inspection of a photomicrograph. (2) The average wavelength is of the order of 1µ. This value is in reasonable agreement with the main wavelength predicted by the theories developed by others. The dependence of wavelength on substrate deposition temperature, alloy composition and the external magnetic field has been also studied and the results are compared with theoretical predictions. (3) The experimental fact that the ripple structure could not be observed in completely epitaxial films gives confirmation that the ripple results from the randomness of crystallite orientation. Furthermore, the experimental observation that the ripple disappeared in the range 71 and 75% Ni supports the theory that the ripple amplitude is directly dependent on the crystalline anisotropy. An attempt to experimentally determine the order of magnitude of the ripple angle was carried out. The measured angle was about 0.02 rad. The discrepancy between the experimental data and the theoretical prediction is serious. The accurate experimental determination of ripple angle is an unsolved problem.