Coding for information storage

Storage systems are widely used and have played a crucial rule in both consumer and industrial products, for example, personal computers, data centers, and embedded systems. However, such system suffers from issues of cost, restricted-lifetime, and reliability with the emergence of new systems and devices, such as distributed storage and flash memory, respectively. Information theory, on the other hand, provides fundamental bounds and solutions to fully utilize resources such as data density, information I/O and network bandwidth. This thesis bridges these two topics, and proposes to solve challenges in data storage using a variety of coding techniques, so that storage becomes faster, more affordable, and more reliable.

We consider the system level and study the integration of RAID schemes and distributed storage. Erasure-correcting codes are the basis of the ubiquitous RAID schemes for storage systems, where disks correspond to symbols in the code and are located in a (distributed) network. Specifically, RAID schemes are based on MDS (maximum distance separable) array codes that enable optimal storage and efficient encoding and decoding algorithms. With r redundancy symbols an MDS code can sustain r erasures. For example, consider an MDS code that can correct two erasures. It is clear that when two symbols are erased, one needs to access and transmit all the remaining information to rebuild the erasures. However, an interesting and practical question is: What is the smallest fraction of information that one needs to access and transmit in order to correct a single erasure? In Part I we will show that the lower bound of 1/2 is achievable and that the result can be generalized to codes with arbitrary number of parities and optimal rebuilding.

We consider the device level and study coding and modulation techniques for emerging non-volatile memories such as flash memory. In particular, rank modulation is a novel data representation scheme proposed by Jiang et al. for multi-level flash memory cells, in which a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. It eliminates the need for discrete cell levels, as well as overshoot errors, when programming cells. In order to decrease the decoding complexity, we propose two variations of this scheme in Part II: bounded rank modulation where only small sliding windows of cells are sorted to generated permutations, and partial rank modulation where only part of the n cells are used to represent data. We study limits on the capacity of bounded rank modulation and propose encoding and decoding algorithms. We show that overlaps between windows will increase capacity. We present Gray codes spanning all possible partial-rank states and using only ``push-to-the-top'' operations. These Gray codes turn out to solve an open combinatorial problem called universal cycle, which is a sequence of integers generating all possible partial permutations.

On erasure coding for distributed storage and streaming communications

The work presented in this thesis revolves around erasure correction coding, as applied to distributed data storage and real-time streaming communications.

First, we examine the problem of allocating a given storage budget over a set of nodes for maximum reliability. The objective is to find an allocation of the budget that maximizes the probability of successful recovery by a data collector accessing a random subset of the nodes. This optimization problem is challenging in general because of its combinatorial nature, despite its simple formulation. We study several variations of the problem, assuming different allocation models and access models, and determine the optimal allocation and the optimal symmetric allocation (in which all nonempty nodes store the same amount of data) for a variety of cases. Although the optimal allocation can have nonintuitive structure and can be difficult to find in general, our results suggest that, as a simple heuristic, reliable storage can be achieved by spreading the budget maximally over all nodes when the budget is large, and spreading it minimally over a few nodes when it is small. Coding would therefore be beneficial in the former case, while uncoded replication would suffice in the latter case.

Second, we study how distributed storage allocations affect the recovery delay in a mobile setting. Specifically, two recovery delay optimization problems are considered for a network of mobile storage nodes: the maximization of the probability of successful recovery by a given deadline, and the minimization of the expected recovery delay. We show that the first problem is closely related to the earlier allocation problem, and solve the second problem completely for the case of symmetric allocations. It turns out that the optimal allocations for the two problems can be quite different. In a simulation study, we evaluated the performance of a simple data dissemination and storage protocol for mobile delay-tolerant networks, and observed that the choice of allocation can have a significant impact on the recovery delay under a variety of scenarios.

Third, we consider a real-time streaming system where messages created at regular time intervals at a source are encoded for transmission to a receiver over a packet erasure link; the receiver must subsequently decode each message within a given delay from its creation time. For erasure models containing a limited number of erasures per coding window, per sliding window, and containing erasure bursts whose maximum length is sufficiently short or long, we show that a time-invariant intrasession code asymptotically achieves the maximum message size among all codes that allow decoding under all admissible erasure patterns. For the bursty erasure model, we also show that diagonally interleaved codes derived from specific systematic block codes are asymptotically optimal over all codes in certain cases. We also study an i.i.d. erasure model in which each transmitted packet is erased independently with the same probability; the objective is to maximize the decoding probability for a given message size. We derive an upper bound on the decoding probability for any time-invariant code, and show that the gap between this bound and the performance of a family of time-invariant intrasession codes is small when the message size and packet erasure probability are small. In a simulation study, these codes performed well against a family of random time-invariant convolutional codes under a number of scenarios.

Finally, we consider the joint problems of routing and caching for named data networking. We propose a backpressure-based policy that employs virtual interest packets to make routing and caching decisions. In a packet-level simulation, the proposed policy outperformed a basic protocol that combines shortest-path routing with least-recently-used (LRU) cache replacement.

Algorithmic challenges in green data centers

With data centers being the supporting infrastructure for a wide range of IT services, their efficiency has become a big concern to operators, as well as to society, for both economic and environmental reasons. The goal of this thesis is to design energy-efficient algorithms that reduce energy cost while minimizing compromise to service. We focus on the algorithmic challenges at different levels of energy optimization across the data center stack. The algorithmic challenge at the device level is to improve the energy efficiency of a single computational device via techniques such as job scheduling and speed scaling. We analyze the common speed scaling algorithms in both the worst-case model and stochastic model to answer some fundamental issues in the design of speed scaling algorithms. The algorithmic challenge at the local data center level is to dynamically allocate resources (e.g., servers) and to dispatch the workload in a data center. We develop an online algorithm to make a data center more power-proportional by dynamically adapting the number of active servers. The algorithmic challenge at the global data center level is to dispatch the workload across multiple data centers, considering the geographical diversity of electricity price, availability of renewable energy, and network propagation delay. We propose algorithms to jointly optimize routing and provisioning in an online manner. Motivated by the above online decision problems, we move on to study a general class of online problem named "smoothed online convex optimization", which seeks to minimize the sum of a sequence of convex functions when "smooth" solutions are preferred. This model allows us to bridge different research communities and help us get a more fundamental understanding of general online decision problems.

Sustainable IT and IT for sustainability

Energy and sustainability have become one of the most critical issues of our generation. While the abundant potential of renewable energy such as solar and wind provides a real opportunity for sustainability, their intermittency and uncertainty present a daunting operating challenge. This thesis aims to develop analytical models, deployable algorithms, and real systems to enable efficient integration of renewable energy into complex distributed systems with limited information.

The first thrust of the thesis is to make IT systems more sustainable by facilitating the integration of renewable energy into these systems. IT represents the fastest growing sectors in energy usage and greenhouse gas pollution. Over the last decade there are dramatic improvements in the energy efficiency of IT systems, but the efficiency improvements do not necessarily lead to reduction in energy consumption because more servers are demanded. Further, little effort has been put in making IT more sustainable, and most of the improvements are from improved "engineering" rather than improved "algorithms". In contrast, my work focuses on developing algorithms with rigorous theoretical analysis that improve the sustainability of IT. In particular, this thesis seeks to exploit the flexibilities of cloud workloads both (i) in time by scheduling delay-tolerant workloads and (ii) in space by routing requests to geographically diverse data centers. These opportunities allow data centers to adaptively respond to renewable availability, varying cooling efficiency, and fluctuating energy prices, while still meeting performance requirements. The design of the enabling algorithms is however very challenging because of limited information, non-smooth objective functions and the need for distributed control. Novel distributed algorithms are developed with theoretically provable guarantees to enable the "follow the renewables" routing. Moving from theory to practice, I helped HP design and implement industry's first Net-zero Energy Data Center.

The second thrust of this thesis is to use IT systems to improve the sustainability and efficiency of our energy infrastructure through data center demand response. The main challenges as we integrate more renewable sources to the existing power grid come from the fluctuation and unpredictability of renewable generation. Although energy storage and reserves can potentially solve the issues, they are very costly. One promising alternative is to make the cloud data centers demand responsive. The potential of such an approach is huge.

To realize this potential, we need adaptive and distributed control of cloud data centers and new electricity market designs for distributed electricity resources. My work is progressing in both directions. In particular, I have designed online algorithms with theoretically guaranteed performance for data center operators to deal with uncertainties under popular demand response programs. Based on local control rules of customers, I have further designed new pricing schemes for demand response to align the interests of customers, utility companies, and the society to improve social welfare.

Strategies for the Stereoselective Synthesis of Carbon Quaternary Centers via Transition Metal-Catalyzed Alkylation of Enolate Compounds

Notwithstanding advances in modern chemical methods, the selective installation of sterically encumbered carbon stereocenters, in particular all-carbon quaternary centers, remains an unsolved problem in organic chemistry. The prevalence of all-carbon quaternary centers in biologically active natural products and pharmaceutical compounds provides a strong impetus to address current limitations in the state of the art of their generation. This thesis presents four related projects, all of which share in the goal of constructing highly-congested carbon centers in a stereoselective manner, and in the use of transition-metal catalyzed alkylation as a means to address that goal.

The first research described is an extension of allylic alkylation methodology previously developed in the Stoltz group to small, strained rings. This research constitutes the first transition metal-catalyzed enantioselective α-alkylation of cyclobutanones. Under Pd-catalysis, this chemistry affords all–carbon α-quaternary cyclobutanones in good to excellent yields and enantioselectivities.

Next is described our development of a (trimethylsilyl)ethyl β-ketoester class of enolate precursors, and their application in palladium–catalyzed asymmetric allylic alkylation to yield a variety of α-quaternary ketones and lactams. Independent coupling partner synthesis engenders enhanced allyl substrate scope relative to allyl β-ketoester substrates; highly functionalized α-quaternary ketones generated by the union of our fluoride-triggered β-ketoesters and sensitive allylic alkylation coupling partners serve to demonstrate the utility of this method for complex fragment coupling.

Lastly, our development of an Ir-catalyzed asymmetric allylic alkylation of cyclic β-ketoesters to afford highly congested, vicinal stereocenters comprised of tertiary and all-carbon quaternary centers with outstanding regio-, diastereo-, and enantiocontrol is detailed. Implementation of a subsequent Pd-catalyzed alkylation affords dialkylated products with pinpoint stereochemical control of both chiral centers. The chemistry is then extended to include acyclic β-ketoesters and similar levels of selective and functional group tolerance are observed. Critical to the successful development of this method was the employment of iridium catalysis in concert with N-aryl-phosphoramidite ligands.

Invariants, Lie-Bäcklund operators and Bäcklund transformations

This thesis is mainly concerned with the application of groups of transformations to differential equations and in particular with the connection between the group structure of a given equation and the existence of exact solutions and conservation laws. In this respect the Lie-Bäcklund groups of tangent transformations, particular cases of which are the Lie tangent and the Lie point groups, are extensively used.

In Chapter I we first review the classical results of Lie, Bäcklund and Bianchi as well as the more recent ones due mainly to Ovsjannikov. We then concentrate on the Lie-Bäcklund groups (or more precisely on the corresponding Lie-Bäcklund operators), as introduced by Ibragimov and Anderson, and prove some lemmas about them which are useful for the following chapters. Finally we introduce the concept of a conditionally admissible operator (as opposed to an admissible one) and show how this can be used to generate exact solutions.

In Chapter II we establish the group nature of all separable solutions and conserved quantities in classical mechanics by analyzing the group structure of the Hamilton-Jacobi equation. It is shown that consideration of only Lie point groups is insufficient. For this purpose a special type of Lie-Bäcklund groups, those equivalent to Lie tangent groups, is used. It is also shown how these generalized groups induce Lie point groups on Hamilton's equations. The generalization of the above results to any first order equation, where the dependent variable does not appear explicitly, is obvious. In the second part of this chapter we investigate admissible operators (or equivalently constants of motion) of the Hamilton-Jacobi equation with polynornial dependence on the momenta. The form of the most general constant of motion linear, quadratic and cubic in the momenta is explicitly found. Emphasis is given to the quadratic case, where the particular case of a fixed (say zero) energy state is also considered; it is shown that in the latter case additional symmetries may appear. Finally, some potentials of physical interest admitting higher symmetries are considered. These include potentials due to two centers and limiting cases thereof. The most general two-center potential admitting a quadratic constant of motion is obtained, as well as the corresponding invariant. Also some new cubic invariants are found.

In Chapter III we first establish the group nature of all separable solutions of any linear, homogeneous equation. We then concentrate on the Schrodinger equation and look for an algorithm which generates a quantum invariant from a classical one. The problem of an isomorphism between functions in classical observables and quantum observables is studied concretely and constructively. For functions at most quadratic in the momenta an isomorphism is possible which agrees with Weyl' s transform and which takes invariants into invariants. It is not possible to extend the isomorphism indefinitely. The requirement that an invariant goes into an invariant may necessitate variants of Weyl' s transform. This is illustrated for the case of cubic invariants. Finally, the case of a specific value of energy is considered; in this case Weyl's transform does not yield an isomorphism even for the quadratic case. However, for this case a correspondence mapping a classical invariant to a quantum orie is explicitly found.

Chapters IV and V are concerned with the general group structure of evolution equations. In Chapter IV we establish a one to one correspondence between admissible Lie-Bäcklund operators of evolution equations (derivable from a variational principle) and conservation laws of these equations. This correspondence takes the form of a simple algorithm.

In Chapter V we first establish the group nature of all Bäcklund transformations (BT) by proving that any solution generated by a BT is invariant under the action of some conditionally admissible operator. We then use an algorithm based on invariance criteria to rederive many known BT and to derive some new ones. Finally, we propose a generalization of BT which, among other advantages, clarifies the connection between the wave-train solution and a BT in the sense that, a BT may be thought of as a variation of parameters of some. special case of the wave-train solution (usually the solitary wave one). Some open problems are indicated.

Most of the material of Chapters II and III is contained in [I], [II], [III] and [IV] and the first part of Chapter V in [V].

Analog VLSI-based, neuromorphic sensorimotor systems: modeling the primate oculomotor system

Using neuromorphic analog VLSI techniques for modeling large neural systems has several advantages over software techniques. By designing massively-parallel analog circuit arrays which are ubiquitous in neural systems, analog VLSI models are extremely fast, particularly when local interactions are important in the computation. While analog VLSI circuits are not as flexible as software methods, the constraints posed by this approach are often very similar to the constraints faced by biological systems. As a result, these constraints can offer many insights into the solutions found by evolution. This dissertation describes a hardware modeling effort to mimic the primate oculomotor system which requires both fast sensory processing and fast motor control. A one-dimensional hardware model of the primate eye has been built which simulates the physical dynamics of the biological system. It is driven by analog VLSI circuits mimicking brainstem and cortical circuits that control eye movements. In this framework, a visually-triggered saccadic system is demonstrated which generates averaging saccades. In addition, an auditory localization system, based on the neural circuits of the barn owl, is used to trigger saccades to acoustic targets in parallel with visual targets. Two different types of learning are also demonstrated on the saccadic system using floating-gate technology allowing the non-volatile storage of analog parameters directly on the chip. Finally, a model of visual attention is used to select and track moving targets against textured backgrounds, driving both saccadic and smooth pursuit eye movements to maintain the image of the target in the center of the field of view. This system represents one of the few efforts in this field to integrate both neuromorphic sensory processing and motor control in a closed-loop fashion.

The Role of Fucose in Learning and Memory: The Identification of a Fucosylprotein, Synapsin I, in the Rat Brain and the Characterization of its Fucosylation

Previous studies have shown that the glycoproteins containing the fucose moiety are involved in neuronal communication phenomena such as long-term potentiation and memory formation. These results imply that fucose containing glycoproteins might play an important role in learning and memory. To understand the role of fucose in neuronal communication, and the mechanisms by which fucose may be involved in information storage, the identification of fucosylproteins is essential. This report describes the identification and characterization of fucosylproteins in the brain, which will provide new insights into the role of the fucose involved molecular interactions.

Cytokine control of neuronal phenotype

Diffusible proteins regulate neural development at a variety of stages. Using a novel neuronal culture assay, I have identified several cytokines that regulate the expression of neurotransmitters and neuropeptides in sympathetic neurons. These cytokines fall into two families. The first group is termed the neuropoietic cytokines, while including CDF/LIF, CNTF, OSM and GPA, induces expression of the same set of neuropeptide mRNAs in cultured sympathetic neurons. These four factors not only exhibit similar biological activities; they also share a predicted secondary structure and bind to a signal-transducing receptor subunit in common with IL-6 and IL-11. The latter two cytokines display a weaker activity in this assay. In addition, I find that several members of the TGF-β superfamily, activin A, BMP-2, and BMP-6, have a selective overlap with the neuropoietic family in the spectrum of neuropeptides that these cytokines induce in sympathetic neurons. Different patterns of neuropeptides induced by the TGF-β family members, however, demonstrate that the activities of these cytokines are distinct from those of the neuropoietic family. Another 30 cytokines are without detectable effect in this neuronal assay.

Activin A induces a set of neurotransmitters and neuropeptides that is somewhat similar to the phenotype of sympathetic neurons innervating sweat glands in rat footpads. In situ hybridization and RNase protection were carried out to test whether activins were involved in the phenotypic transition when sympathetic neurons contact sweat glands. I find that activin mRNA is present in both cholinergic and noradrenergic targets. Moreover, homogenates of footpads do not contain activin-like activity in the neuronal assay in vitro. Taken together, these data do not support activins as the best candidates for the sweat gland factor.

Several novel factors that regulate neuropeptide expression exist in heart cell conditioned medium. I attempted to purify these factors in collaboration with Dr. Jane Talvenheimo. Our results suggest that these factors are sensitive to the storage conditions used. Several modifications of purification strategy are discussed.

Structural and mechanistic study of monoalkyl diazenes. Synthesis, characterization, and reactivity of 1,6-didehydro[10]annulene

Methodology for the preparation of allenes from propargylic hydrazine precursors under mild conditions is described. Oxidation of the propargylic hydrazines, which can be readily prepared from propargylic alcohols, with either of two azo oxidants, diethyl azodicarboxylate (DEAD) or 4-methyl 1,2-triazoline-3,5-dione (MTAD), effects conversion to the allenes, presumably via sigmatropic rearrangement of a monoalkyl diazene intermediate. This rearrangement is demonstrated to proceed with essentially complete stereospecificity. The application of this methodology to the preparation of other allenes, including two that are notable for their reactivity and thermal instability, is also described.

The structural and mechanistic study of a monoalkyl diazene intermediate in the oxidative transformation of propargylic hydrazines to allenes is described. The use of long-range heteronuclear NMR coupling constants for assigning monoalkyl diazene stereochemistry (E vs Z) is also discussed. Evidence is presented that all known monoalkyl diazenes are the E isomers, and the erroneous assignment of stereochemistry in the previous report of the preparation of (Z)-phenyldiazene is discussed.

The synthesis, characterization, and reactivity of 1,6-didehydro[10]annulene are described. This molecule has been recognized as an interesting synthetic target for over 40 years and represents the intersection of two sets of extensively studied molecules: nonbenzenoid aromatic compounds and molecules containing sterically compressed π-systems.The formation of 1,5-dehydronaphthalene from 1 ,6-didehydro[10]annulene is believed to be the prototype for cycloaromatizations that produce 1,4-dehydroaromatic species with the radical centers disposed anti about the newly formed single bond. The aromaticity of this annulene and the facility of its cycloaromatization are also analyzed.

The electrocatalytic and stoichiometric oxidation chemistry of binuclear ruthenium complexes incorporating the anionic tripod ligand {(η5-C5H5)Co[P(OCH3)2(=O)]3}-

The anionic tripod ligand NaLoMe (L_(oMe) - = [(η^5-C_5H_5)Co{P(O)(OCH_3)_2}_3]^-) reacts with RuO_4 in a biphasic reaction mixture of 1% H_2SO_4 and CCI_4 to afford [(L_(oMe) (HO)Ru^(IV) (µ-O)_2Ru ^(IV)(OH)(L_(oMe)] (1), which is treated with aqueous CF_3S0_3H to generate [(L_(oMe)(H_2O)Ru^(IV) (µ-O)_2R^(IV) (OH_2)(L_(oMe)][CF_3SO_3]_2 ([H_21][CF_3SO_3]_2). Addition of iodosobenzene to an acetonitrile solution of this salt yields [(L_(oMe)(O)Ru^v(µ-0)2Ru^v-(O)(_(LoMe)] (2). The dimer 1 can be reduced chemically or electrochemically to the Ru^(III)- Ru^(III) dimers [(L_(oMe)(H_20)Ru^(III) (µ-OH)_2Ru^(III) (OH_2)(L_(oMe)) ]^2+ and [(L_(oMe)) ^(III) (µ-0Hh(µ-0H2)Ru^(III) (L_(oMe)]^2+ which interconvert in aqueous media. Two electron processes dominate both the bulk chemistry and the electrochemistry of 1. Among these processes are the quasi-reversible Ru^(IV) - Ru^(IV)/Ru^(III)- Ru^(III) and Ru^(III)- Ru^(III)/ Ru^(II)- Ru^(II) reductions and a largely irreversible Ru^(V) - Ru^(V)/ Ru^(IV) - Ru^(IV)/oxidation. The dioxo dimer 2 oxidizes alcohols and aldehydes in organic media to afford 1 and the corresponding aldehydes and acids. Analogously, the Ru^(V) - Ru^(V)/ Ru^(IV)- Ru^(IV) redox wave mediates the electrooxidation of alcohols and aldehydes in aqueous buffer. In this system, substrates can be oxidized completely to CO_2. The kinetic behavior of these oxidations was examined by UV-vis and chronoamperometry, respectively, and the chemistry is typical of metal-oxo complexes, indicating that electronic coupling between two metal centers does not dramatically affect the metal-oxo chemistry. Dimer [H_21]^(2+) also reacts with alcohols, aldehydes, and triphenylphosphine in CH_3CN to afford Ru^(III)- Ru^(III) products including [(L_(oMe))CH_3CN) Ru^(III) (µ-OH)_2 Ru^(III) (NCCH_3)( L_(oMe))][CF_3SO_3]2 (characterized by X-ray crystallography) and the corresponding organic products. Reaction of 1 with formaldehyde in aqueous buffer quantitatively affords the triply bridged dimer [(L_(oMe)Ru^(III) (µ-OH)2- (µ-HCOO) Ru^(III) (L_(oMe)][CF_3SO_3] (characterized by X-ray crystallography). This reaction evidently proceeds by two parallel inner-sphere pathways, one of which is autocatalytic. Neither pathway exhibits a primary isotope effect suggesting the rate determining process could be the formation of an intermediate, perhaps a Ru^(IV) - Ru^(IV) formate adduct. The Ru^(III)- Ru^(III)formate adduct is easily oxidized to the Ru^(IV) - Ru^(IV) analog [(L_(oMe)Ru^(IV)(µ-OH)_2-(µ-HCOO) Ru^(IV) (L_(oMe)][CF_3SO_3], which, after isolation, reacts slowly with aqueous formaldehyde to generate free formate and the Ru^(III)- Ru^(III) formate adduct. These dimers function as catalysts for the electrooxidation of formaldehyde at low anodic potentials (+0.0 V versus SCE in aqueous buffer, pH 8.5) and enhance the activity of Nafion treated palladium/carbon heterogeneous fuel cell catalysts.

Synthesis, structure, and photophysics of polypyridophenazine transition-metal complexes

The condensation of phenanthroline-5,6-dione (phendione) with polyamines is a versatile synthetic route to a wide variety of chelating ligands. Condensation with 2,3- napthalene diamine gives benzo[i]dipyrido[3,2-a:2',3'-c]phenazine (bdppz) a ligand containing weakly-coupled orbitals of benzophenazine (bpz) and 2,2' -bipyridinde(bpy) character. The bpy character gives Re and Ru complexes excited-state redox properties; intramolecular electron transfer (ET) takes place to the bpz portion of the ligand. The charge-separated state so produced has an extraordinarily-long 50 µs lifetime. The slow rate of charge recombination arises from a combination of extremely weak coupling between the metal center and the bpz acceptor orbital and Marcus "inverted region" behavior. Molecular orbital calculations show that only 3% the electron density in the lowest unoccupied molecular orbital lies on the bpy atoms of bdppz, effectively trapping the transferred electron on the bpz portion. The rate of charge recombination decreases with increasing driving force, showing that these rates lie in the inverted region. Comparison of forward and back ET rates shows that donor-acceptor coupling is four orders of magnitude greater for photoinduced electron transfer than it is for thermal charge recombination.

Condensation of phendione with itself or tetramines gives a series of binucleating tetrapyridophenazine ligands of incrementally-varying coordination-site separation. When a photoredox-active metal center is attached, excited-state energy and electron transfer to an acceptor metal center at the other coordination site can be studied as a function of distance. A variety of monometallic and homo- and heterodimetallic tetrapyridophenazine complexes has been synthesized. Electro- and magnetochemistry show that no ground-state interaction exists between the metals in bimetallic complexes. Excited-state energy and electron transfer, however, takes place at rates which are invariant with increasing donor-acceptor separation, indicating that a very efficient coupling mechanism is at work. Theory and experiment have suggested that such behavior might exist in extended π-systems like those presented by these ligands.

Condensation of three equivalents of 4,5-dimethyl-1,2-phenylenediamine with hexaketocyclohexane gives the trinucleating ligand hexaazahexamethyltrinapthalene (hhtn). Attaching two photredox-active metal centers and a third catalytic center to hhtn provides means by which multielectron photocatalyzed reactions might be carried out. The coordination properties of hhtn have been examined; X-ray crystallographic structure determination shows that the ligand's constricted coordination pocket leads to distorted geometries in its mono- and dimetallic derivatives.

Topics in gravitational-wave science : macroscopic quantum mechanics and black hole physics

The theories of relativity and quantum mechanics, the two most important physics discoveries of the 20th century, not only revolutionized our understanding of the nature of space-time and the way matter exists and interacts, but also became the building blocks of what we currently know as modern physics. My thesis studies both subjects in great depths --- this intersection takes place in gravitational-wave physics.

Gravitational waves are "ripples of space-time", long predicted by general relativity. Although indirect evidence of gravitational waves has been discovered from observations of binary pulsars, direct detection of these waves is still actively being pursued. An international array of laser interferometer gravitational-wave detectors has been constructed in the past decade, and a first generation of these detectors has taken several years of data without a discovery. At this moment, these detectors are being upgraded into second-generation configurations, which will have ten times better sensitivity. Kilogram-scale test masses of these detectors, highly isolated from the environment, are probed continuously by photons. The sensitivity of such a quantum measurement can often be limited by the Heisenberg Uncertainty Principle, and during such a measurement, the test masses can be viewed as evolving through a sequence of nearly pure quantum states.

The first part of this thesis (Chapter 2) concerns how to minimize the adverse effect of thermal fluctuations on the sensitivity of advanced gravitational detectors, thereby making them closer to being quantum-limited. My colleagues and I present a detailed analysis of coating thermal noise in advanced gravitational-wave detectors, which is the dominant noise source of Advanced LIGO in the middle of the detection frequency band. We identified the two elastic loss angles, clarified the different components of the coating Brownian noise, and obtained their cross spectral densities.

The second part of this thesis (Chapters 3-7) concerns formulating experimental concepts and analyzing experimental results that demonstrate the quantum mechanical behavior of macroscopic objects - as well as developing theoretical tools for analyzing quantum measurement processes. In Chapter 3, we study the open quantum dynamics of optomechanical experiments in which a single photon strongly influences the quantum state of a mechanical object. We also explain how to engineer the mechanical oscillator's quantum state by modifying the single photon's wave function.

In Chapters 4-5, we build theoretical tools for analyzing the so-called "non-Markovian" quantum measurement processes. Chapter 4 establishes a mathematical formalism that describes the evolution of a quantum system (the plant), which is coupled to a non-Markovian bath (i.e., one with a memory) while at the same time being under continuous quantum measurement (by the probe field). This aims at providing a general framework for analyzing a large class of non-Markovian measurement processes. Chapter 5 develops a way of characterizing the non-Markovianity of a bath (i.e.,whether and to what extent the bath remembers information about the plant) by perturbing the plant and watching for changes in the its subsequent evolution. Chapter 6 re-analyzes a recent measurement of a mechanical oscillator's zero-point fluctuations, revealing nontrivial correlation between the measurement device's sensing noise and the quantum rack-action noise.

Chapter 7 describes a model in which gravity is classical and matter motions are quantized, elaborating how the quantum motions of matter are affected by the fact that gravity is classical. It offers an experimentally plausible way to test this model (hence the nature of gravity) by measuring the center-of-mass motion of a macroscopic object.

The most promising gravitational waves for direct detection are those emitted from highly energetic astrophysical processes, sometimes involving black holes - a type of object predicted by general relativity whose properties depend highly on the strong-field regime of the theory. Although black holes have been inferred to exist at centers of galaxies and in certain so-called X-ray binary objects, detecting gravitational waves emitted by systems containing black holes will offer a much more direct way of observing black holes, providing unprecedented details of space-time geometry in the black-holes' strong-field region.

The third part of this thesis (Chapters 8-11) studies black-hole physics in connection with gravitational-wave detection.

Chapter 8 applies black hole perturbation theory to model the dynamics of a light compact object orbiting around a massive central Schwarzschild black hole. In this chapter, we present a Hamiltonian formalism in which the low-mass object and the metric perturbations of the background spacetime are jointly evolved. Chapter 9 uses WKB techniques to analyze oscillation modes (quasi-normal modes or QNMs) of spinning black holes. We obtain analytical approximations to the spectrum of the weakly-damped QNMs, with relative error O(1/L^2), and connect these frequencies to geometrical features of spherical photon orbits in Kerr spacetime. Chapter 11 focuses mainly on near-extremal Kerr black holes, we discuss a bifurcation in their QNM spectra for certain ranges of (l,m) (the angular quantum numbers) as a/M → 1. With tools prepared in Chapter 9 and 10, in Chapter 11 we obtain an analytical approximate for the scalar Green function in Kerr spacetime.

Electrical and optical interconnects for high-performance computing

Technology scaling has enabled drastic growth in the computational and storage capacity of integrated circuits (ICs). This constant growth drives an increasing demand for high-bandwidth communication between and within ICs. In this dissertation we focus on low-power solutions that address this demand. We divide communication links into three subcategories depending on the communication distance. Each category has a different set of challenges and requirements and is affected by CMOS technology scaling in a different manner. We start with short-range chip-to-chip links for board-level communication. Next we will discuss board-to-board links, which demand a longer communication range. Finally on-chip links with communication ranges of a few millimeters are discussed.

Electrical signaling is a natural choice for chip-to-chip communication due to efficient integration and low cost. IO data rates have increased to the point where electrical signaling is now limited by the channel bandwidth. In order to achieve multi-Gb/s data rates, complex designs that equalize the channel are necessary. In addition, a high level of parallelism is central to sustaining bandwidth growth. Decision feedback equalization (DFE) is one of the most commonly employed techniques to overcome the limited bandwidth problem of the electrical channels. A linear and low-power summer is the central block of a DFE. Conventional approaches employ current-mode techniques to implement the summer, which require high power consumption. In order to achieve low-power operation we propose performing the summation in the charge domain. This approach enables a low-power and compact realization of the DFE as well as crosstalk cancellation. A prototype receiver was fabricated in 45nm SOI CMOS to validate the functionality of the proposed technique and was tested over channels with different levels of loss and coupling. Measurement results show that the receiver can equalize channels with maximum 21dB loss while consuming about 7.5mW from a 1.2V supply. We also introduce a compact, low-power transmitter employing passive equalization. The efficacy of the proposed technique is demonstrated through implementation of a prototype in 65nm CMOS. The design achieves up to 20Gb/s data rate while consuming less than 10mW.

An alternative to electrical signaling is to employ optical signaling for chip-to-chip interconnections, which offers low channel loss and cross-talk while providing high communication bandwidth. In this work we demonstrate the possibility of building compact and low-power optical receivers. A novel RC front-end is proposed that combines dynamic offset modulation and double-sampling techniques to eliminate the need for a short time constant at the input of the receiver. Unlike conventional designs, this receiver does not require a high-gain stage that runs at the data rate, making it suitable for low-power implementations. In addition, it allows time-division multiplexing to support very high data rates. A prototype was implemented in 65nm CMOS and achieved up to 24Gb/s with less than 0.4pJ/b power efficiency per channel. As the proposed design mainly employs digital blocks, it benefits greatly from technology scaling in terms of power and area saving.

As the technology scales, the number of transistors on the chip grows. This necessitates a corresponding increase in the bandwidth of the on-chip wires. In this dissertation, we take a close look at wire scaling and investigate its effect on wire performance metrics. We explore a novel on-chip communication link based on a double-sampling architecture and dynamic offset modulation technique that enables low power consumption and high data rates while achieving high bandwidth density in 28nm CMOS technology. The functionality of the link is demonstrated using different length minimum-pitch on-chip wires. Measurement results show that the link achieves up to 20Gb/s of data rate (12.5Gb/s/$\mu$m) with better than 136fJ/b of power efficiency.

Lattice quantum codes and exotic topological phases of matter

This thesis addresses whether it is possible to build a robust memory device for quantum information. Many schemes for fault-tolerant quantum information processing have been developed so far, one of which, called topological quantum computation, makes use of degrees of freedom that are inherently insensitive to local errors. However, this scheme is not so reliable against thermal errors. Other fault-tolerant schemes achieve better reliability through active error correction, but incur a substantial overhead cost. Thus, it is of practical importance and theoretical interest to design and assess fault-tolerant schemes that work well at finite temperature without active error correction.

In this thesis, a three-dimensional gapped lattice spin model is found which demonstrates for the first time that a reliable quantum memory at finite temperature is possible, at least to some extent. When quantum information is encoded into a highly entangled ground state of this model and subjected to thermal errors, the errors remain easily correctable for a long time without any active intervention, because a macroscopic energy barrier keeps the errors well localized. As a result, stored quantum information can be retrieved faithfully for a memory time which grows exponentially with the square of the inverse temperature. In contrast, for previously known types of topological quantum storage in three or fewer spatial dimensions the memory time scales exponentially with the inverse temperature, rather than its square.

This spin model exhibits a previously unexpected topological quantum order, in which ground states are locally indistinguishable, pointlike excitations are immobile, and the immobility is not affected by small perturbations of the Hamiltonian. The degeneracy of the ground state, though also insensitive to perturbations, is a complicated number-theoretic function of the system size, and the system bifurcates into multiple noninteracting copies of itself under real-space renormalization group transformations. The degeneracy, the excitations, and the renormalization group flow can be analyzed using a framework that exploits the spin model's symmetry and some associated free resolutions of modules over polynomial algebras.