Information-theoretic analysis of a stimulated-Brillouin-scattering-based slow-light system.

We use an information-theoretic method developed by Neifeld and Lee [J. Opt. Soc. Am. A 25, C31 (2008)] to analyze the performance of a slow-light system. Slow-light is realized in this system via stimulated Brillouin scattering in a 2 km-long, room-temperature, highly nonlinear fiber pumped by a laser whose spectrum is tailored and broadened to 5 GHz. We compute the information throughput (IT), which quantifies the fraction of information transferred from the source to the receiver and the information delay (ID), which quantifies the delay of a data stream at which the information transfer is largest, for a range of experimental parameters. We also measure the eye-opening (EO) and signal-to-noise ratio (SNR) of the transmitted data stream and find that they scale in a similar fashion to the information-theoretic method. Our experimental findings are compared to a model of the slow-light system that accounts for all pertinent noise sources in the system as well as data-pulse distortion due to the filtering effect of the SBS process. The agreement between our observations and the predictions of our model is very good. Furthermore, we compare measurements of the IT for an optimal flattop gain profile and for a Gaussian-shaped gain profile. For a given pump-beam power, we find that the optimal profile gives a 36% larger ID and somewhat higher IT compared to the Gaussian profile. Specifically, the optimal (Gaussian) profile produces a fractional slow-light ID of 0.94 (0.69) and an IT of 0.86 (0.86) at a pump-beam power of 450 mW and a data rate of 2.5 Gbps. Thus, the optimal profile better utilizes the available pump-beam power, which is often a valuable resource in a system design.

Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

Role of DNA binding sites and slow unbinding kinetics in titration-based oscillators.

Genetic oscillators, such as circadian clocks, are constantly perturbed by molecular noise arising from the small number of molecules involved in gene regulation. One of the strongest sources of stochasticity is the binary noise that arises from the binding of a regulatory protein to a promoter in the chromosomal DNA. In this study, we focus on two minimal oscillators based on activator titration and repressor titration to understand the key parameters that are important for oscillations and for overcoming binary noise. We show that the rate of unbinding from the DNA, despite traditionally being considered a fast parameter, needs to be slow to broaden the space of oscillatory solutions. The addition of multiple, independent DNA binding sites further expands the oscillatory parameter space for the repressor-titration oscillator and lengthens the period of both oscillators. This effect is a combination of increased effective delay of the unbinding kinetics due to multiple binding sites and increased promoter ultrasensitivity that is specific for repression. We then use stochastic simulation to show that multiple binding sites increase the coherence of oscillations by mitigating the binary noise. Slow values of DNA unbinding rate are also effective in alleviating molecular noise due to the increased distance from the bifurcation point. Our work demonstrates how the number of DNA binding sites and slow unbinding kinetics, which are often omitted in biophysical models of gene circuits, can have a significant impact on the temporal and stochastic dynamics of genetic oscillators.

Slow light with a swept-frequency source.

ct: We introduce a new concept for stimulated-Brillouin-scattering-based slow light in optical fibers that is applicable for broadly-tunable frequency-swept sources. It allows slow light to be achieved, in principle, over the entire transparency window of the optical fiber. We demonstrate a slow light delay of 10 ns at 1.55 μm using a 10-m-long photonic crystal fiber with a source sweep rate of 400 MHz/μs and a pump power of 200 mW. We also show that there exists a maximal delay obtainable by this method, which is set by the SBS threshold, independent of sweep rate. For our fiber with optimum length, this maximum delay is ~38 ns, obtained for a pump power of 760 mW.

High-fidelity, broadband stimulated-Brillouin-scattering-based slow light using fast noise modulation.

We demonstrate a 5-GHz-broadband tunable slow-light device based on stimulated Brillouin scattering in a standard highly-nonlinear optical fiber pumped by a noise-current-modulated laser beam. The noisemodulation waveform uses an optimized pseudo-random distribution of the laser drive voltage to obtain an optimal flat-topped gain profile, which minimizes the pulse distortion and maximizes pulse delay for a given pump power. In comparison with a previous slow-modulation method, eye-diagram and signal-to-noise ratio (SNR) analysis show that this broadband slow-light technique significantly increases the fidelity of a delayed data sequence, while maintaining the delay performance. A fractional delay of 0.81 with a SNR of 5.2 is achieved at the pump power of 350 mW using a 2-km-long highly nonlinear fiber with the fast noise-modulation method, demonstrating a 50% increase in eye-opening and a 36% increase in SNR in the comparison.

Delay activity of saccade-related neurons in the caudal dentate nucleus of the macaque cerebellum.

The caudal dentate nucleus (DN) in lateral cerebellum is connected with two visual/oculomotor areas of the cerebrum: the frontal eye field and lateral intraparietal cortex. Many neurons in frontal eye field and lateral intraparietal cortex produce "delay activity" between stimulus and response that correlates with processes such as motor planning. Our hypothesis was that caudal DN neurons would have prominent delay activity as well. From lesion studies, we predicted that this activity would be related to self-timing, i.e., the triggering of saccades based on the internal monitoring of time. We recorded from neurons in the caudal DN of monkeys (Macaca mulatta) that made delayed saccades with or without a self-timing requirement. Most (84%) of the caudal DN neurons had delay activity. These neurons conveyed at least three types of information. First, their activity was often correlated, trial by trial, with saccade initiation. Correlations were found more frequently in a task that required self-timing of saccades (53% of neurons) than in a task that did not (27% of neurons). Second, the delay activity was often tuned for saccade direction (in 65% of neurons). This tuning emerged continuously during a trial. Third, the time course of delay activity associated with self-timed saccades differed significantly from that associated with visually guided saccades (in 71% of neurons). A minority of neurons had sensory-related activity. None had presaccadic bursts, in contrast to DN neurons recorded more rostrally. We conclude that caudal DN neurons convey saccade-related delay activity that may contribute to the motor preparation of when and where to move.