Dimensions, issues, and bills: Appropriations voting on the house floor

One of the fundamental findings in the congressional literature is that one or sometimes two dimensions can successfully describe roll-call voting. In this paper we investigate if we can reach the same conclusions about low dimensionality when we divide the roll-call agenda into subsets of relatively homogeneous subject matter. We are primarily interested in the degree to which the same ordering of representatives is yielded across these different groups of votes. To conduct our analysis we focus on all roll calls on the 13 annual appropriations bills across eight congresses. When we concentrate on these smaller issue areas, we find that voting is multidimensional and members do not vote in a consistent ideological fashion across all issue areas. Copyright © Southern Political Science Association 2010.

Compressive holography.

Compressive sampling enables signal reconstruction using less than one measurement per reconstructed signal value. Compressive measurement is particularly useful in generating multidimensional images from lower dimensional data. We demonstrate single frame 3D tomography from 2D holographic data.

Memory and coping with stress: the relationship between cognitive-emotional distinctiveness, memory valence, and distress.

Cognitive-emotional distinctiveness (CED), the extent to which an individual separates emotions from an event in the cognitive representation of the event, was explored in four studies. CED was measured using a modified multidimensional scaling procedure. The first study found that lower levels of CED in memories of the September 11 terrorist attacks predicted greater frequency of intrusive thoughts about the attacks. The second study revealed that CED levels are higher in negative events, in comparison to positive events and that low CED levels in emotionally intense negative events are associated with a pattern of greater event-related distress. The third study replicated the findings from the previous study when examining CED levels in participants' memories of the 2004 Presidential election. The fourth study revealed that low CED in emotionally intense negative events is associated with worse mental health. We argue that CED is an adaptive and healthy coping feature of stressful memories.

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.