Overview of FEED, the feeding experiments end-user database.

The Feeding Experiments End-user Database (FEED) is a research tool developed by the Mammalian Feeding Working Group at the National Evolutionary Synthesis Center that permits synthetic, evolutionary analyses of the physiology of mammalian feeding. The tasks of the Working Group are to compile physiologic data sets into a uniform digital format stored at a central source, develop a standardized terminology for describing and organizing the data, and carry out a set of novel analyses using FEED. FEED contains raw physiologic data linked to extensive metadata. It serves as an archive for a large number of existing data sets and a repository for future data sets. The metadata are stored as text and images that describe experimental protocols, research subjects, and anatomical information. The metadata incorporate controlled vocabularies to allow consistent use of the terms used to describe and organize the physiologic data. The planned analyses address long-standing questions concerning the phylogenetic distribution of phenotypes involving muscle anatomy and feeding physiology among mammals, the presence and nature of motor pattern conservation in the mammalian feeding muscles, and the extent to which suckling constrains the evolution of feeding behavior in adult mammals. We expect FEED to be a growing digital archive that will facilitate new research into understanding the evolution of feeding anatomy.

Cognitive control of movement via the cerebellar-recipient thalamus.

The cognitive control of behavior was long considered to be centralized in cerebral cortex. More recently, subcortical structures such as cerebellum and basal ganglia have been implicated in cognitive functions as well. The fact that subcortico-cortical circuits for the control of movement involve the thalamus prompts the notion that activity in movement-related thalamus may also reflect elements of cognitive behavior. Yet this hypothesis has rarely been investigated. Using the pathways linking cerebellum to cerebral cortex via the thalamus as a template, we review evidence that the motor thalamus, together with movement-related central thalamus have the requisite connectivity and activity to mediate cognitive aspects of movement control.

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.

Long-duration animal tracking in difficult lighting conditions.

High-throughput analysis of animal behavior requires software to analyze videos. Such software typically depends on the experiments' being performed in good lighting conditions, but this ideal is difficult or impossible to achieve for certain classes of experiments. Here, we describe techniques that allow long-duration positional tracking in difficult lighting conditions with strong shadows or recurring "on"/"off" changes in lighting. The latter condition will likely become increasingly common, e.g., for Drosophila due to the advent of red-shifted channel rhodopsins. The techniques enabled tracking with good accuracy in three types of experiments with difficult lighting conditions in our lab. Our technique handling shadows relies on single-animal tracking and on shadows' and flies' being accurately distinguishable by distance to the center of the arena (or a similar geometric rule); the other techniques should be broadly applicable. We implemented the techniques as extensions of the widely-used tracking software Ctrax; however, they are relatively simple, not specific to Drosophila, and could be added to other trackers as well.