## SSS Abstracts |

In this talk I will review the general setup of the optimal combinatorial auction design problem. I will also introduce one of the promising approaches to the problem, which focuses on designing approximations (suboptimal auction mechanisms which yield high revenue) rather than attempting to characterize the optimal mechanism itself. Finally I will present the approximation results obtained in worst-case and average-case frameworks.

This is joint work with Tuomas Sandholm.

This talk is in partial fulfillment of the speaking requirement.

This is joint work with Tuomas Sandholm.

This talk is in partial fulfillment of the speaking requirement.

We propose the use of a self-organizing hierarchical runtime framework that provides automatic handling of these issues for the logical system processes, such as balance, motion planning, and sensor aggregation. In this talk, I will provide an overview of the structure and function of the Claytronics hierarchy system. No previous knowledge of Claytronics, networking, or related sensor network systems is presumed.

This is joint work with Phillip B. Gibbons, Srinivasan Seshan, Padmanabhan Pillai, Todd C. Mowry, and Seth Copen Goldstein.

This talk is in partial fulfillment of the speaking requirement.

This talk is intended as an introduction to modal logic for a general computer science audience. The speaker's own work on a modal distributed programming language will be used as a motivating example.

This talk is in partial fulfillment of the speaking requirement.

If the images were text documents, we could find the main terms and concepts for each condition by existing IR methods (e.g., tf/idf and LSI). We propose something analogous, but for the much more challenging case of an image collection: We propose to automatically develop a visual vocabulary by breaking images into n*n tiles and deriving key tiles ("ViVos") for each image and condition. We experiment with numerous domain-independent ways of extracting features from tiles (color histograms, textures, etc.), and several ways of choosing characteristic tiles (PCA, ICA).

We perform experiments on two disparate biomedical datasets. The quantitative measure of success is classification accuracy: Our "ViVos" achieve excellent classification accuracy (up to 83% for a nine-class problem for the cat retinal images). More importantly, qualitatively, our "ViVos" do an excellent job as "visual vocabulary terms": they have biological meaning, as corroborated by domain experts; they help spot characteristic regions of images, exactly like text vocabulary terms do for documents; and they highlight the differences between pairs of images.

This is joint work with Arnab Bhattacharya, Vebjorn Ljosa, Mark R. Verardo, Hyungjeong Yang, Christos Faloutsos and Ambuj K. Singh.

This talk is in partial fulfillment of the speaking requirement.

In this talk, I will present a mini-review, suitable for a general computer science audience, of how monads are used for including effects such as I/O and mutation in purely functional languages. I will then show how we can further refine monadic types into a form suitable for reasoning about security.

This is joint work with Karl Crary and Frank Pfenning.

This talk is in partial fulfillment of the speaking requirement.

This talk is in partial fulfillment of the speaking requirement.

This talk is in partial fulfillment of the Speaking Skills Requirement.

This talk is in partial fulfillment of the speaking requirement.

In this talk I will describe the application of predicate abstraction for verification of hardware designs given in Verilog. The two main challenges when applying predicate abstraction are: 1) discovery of suitable predicates. 2) computation of predicate abstraction in presence of large number of predicates. I will describe the techniques for addressing these problems and present encouraging experimental results.

This is joint work with Daniel Kroening, Natasha Sharygina, Edmund Clarke.

This talk is in partial fulfillment of the speaking requirement.

Extreme value theory attempts to make meaningful statements about the probability of as-yet-unprecedented events. A surprising result is that, under fairly mild statistical assumptions, the probability is actually well-defined. Specifically, under certain regularity conditions, the maximum of n independent and identically distributed random variables must asymptotically follow one of three "generalized extreme value" (GEV) distributions. Estimating the parameters of the GEV distribution allows one to draw inferences about its upper tail, including portions of the tail for which there is no observed data.

In the first half of this talk I will give a self-contained introduction to extreme value theory, including a sketch of the proof of its main theorem. I will then present the "max k-armed bandit problem", a previously-studied problem that is motivated by extreme value theory and has applications to combinatorial optimization. The problem asks: given k "payoff" distributions, each a GEV distribution with unknown parameters, how can we sample the distributions so as to maximize the expected maximum payoff obtained after n samples? I will outline an asymptotically optimal algorithm for the problem. Specifically, I will describe a strategy that obtains expected maximum payoff within o(1) of that obtained by a strategy that plays optimally knowing the true parameters of each distribution.

Joint work with Steve Smith. This talk is in partial fulfillment of the speaking requirement.