Combinatorial optimization  captures many natural problems such as matching, load balancing, social welfare, orienteering, network design, clustering, and submodular optimization. Classically, these problems have been studied in the full-information setting, i.e., where the entire input---an objective function with some constraints---is given and the goal is to select a feasible set to maximize/minimize the objective function. In this thesis we focus on combinatorial  problems in an uncertain environment where we only have partial knowledge about the input. In particular, we study  models where  uncertainty in the input is revealed to us element-by-element, and we have to make immediate and irrevocable decisions. Depending on whether we can control the revelation order of these elements, we separate our  models and algorithms into two classes.

(a) Probing Algorithms: In these models we have some stochastic knowledge about the input, but the uncertainty of an element realizes only after we probe it. We can choose the order and the set of elements to probe; however, we do not wish to probe all of them as either probing incurs a price (the price of information model) or there are probing constraints (the constrained stochastic probing model). Some examples are the Pandora's box and the best-box problems.

(b) Stopping-Time Algorithms: In these models the uncertainty in the input is revealed element-by-element in an order  that we cannot control. These models are inspired from work in the field of Stopping Theory. In particular, we consider combinatorial problems when the revelation order is either chosen by an adversary (the Prophet Inequality model) or chosen uniformly at random (the Secretary model).

Thesis Committee:
Manuel Blum (Co-chair)
Anupam Gupta (Co-chair)
R. Ravi
Robert D. Kleinberg (Cornell University)
Jan Vondrak (Stanford University)

Copy of Thesis Summary

Multicore processors are becoming increasingly prevalent, blurring the lines between traditional parallel programs, which use cooperative threading to reduce execution time, and interactive programs which use competitive threading to increase responsiveness. To assist programmers in developing this new class of responsive parallel programs which use threads for both of these purposes, I propose a model that combines the cooperative and competitive paradigms.  The proposed model spans many levels of abstraction. The first component is a cost model that extends existing models of cooperative threading in order to allow programmers to reason about the parallel running time and the responsiveness of responsive parallel applications. The second is a language that neatly combines abstractions for both forms of threading, and enables reasoning about efficiency and responsiveness at the level of the source code. As a final component, I propose to implement the language as part of a compiler for Standard ML, and evaluate it on a benchmark suite including a number of realistic responsive parallel applications.

Thesis Committee:
Umut Acar (Chair)
Guy Blelloch
Mor Harchol-Balter
Robert Harper
John Reppy (University of Chicago)
Vijay Saraswat (IBM TJ Watson Research Center)

Copy of Proposal Document

You are invited to attend this year's viewing of student work on the PauschBridge.  The goal of this course is bring students together from across disciplines to honor the memory of Randy Pausch by creating dynamic interactive light shows.

Projects include:

Students: Roman Baiocco, Kenny Cohen, David Murray, Alex O'Neill, Nick Roberts

The Randy Pausch Memorial Bridge exists as both a physical and conceptual connection between computer science and the arts on Carnegie Mellon's campus. 15-Love expands on this cross-disciplinary nature to allow for users to interact with the bridge in a game like fashion. 15-Love, at its core, is simply a game of tennis experienced through light. The game utilizes moon tracking technology to detect player movements, which are then sent to the bridge. Players on opposite ends of the bridge compete for glory.

Story Animator
Students: Aisha Dev, Naomi Laguerre, Emily Newman, Nitsan Shai

It is often said that a picture is worth a thousand words. With the added dimension of time, can one argue that a moving picture is worth more? This project allows users to tell a story through light. Using color and intensity, users will be able to paint select scenes from a beloved childhood story on the Pausch Bridge. In the end, all scenes will stitch together and playback to bring the story to life (light)!

Campus Mood Ring
Students: Allson Fisher, Leo Galvan, Monica Huang, Soonho Kwon, Jun Ma

Campus Mood Ring is an interacve data visualizaon of the current mood of CMU students. Motivated by the importance of mental health at CMU, Campus Mood Ring aims to reflect and balance the moods of members of the CMU community. In addition to the collective mood visualization, Campus Mood Ring also provides a personal, immersive light show experience to help empathize with students crossing the Pausch Bridge at night.

Course Faculty:
Cindy Limauro, School of Drama (and Co-Lighting Designer with Christopher Popowich of the Pausch Bridge), with
Evan Shimizu, Ph.D. Student, Computer Science Department, School of Computer Science

Subscribe to CSD/Drama