^June July – 2009 ^August

We consider the following sequential decision problem. Given a set of items of unknown utility, we need to select one of as high a utility as possible (``the selection problem''). Measurements (possibly noisy) of item values prior to selection are allowed, at a known cost. The goal is to optimize the overall sequential decision process of measurements and selection. Value of information (VOI) is a well-known scheme for selecting measurements, but the intractability of the problem typically leads to using myopic VOI estimates. In the selection problem, myopic VOI frequently badly underestimates the value of information, leading to inferior sensing plans. We relax the strict myopic assumption into a scheme we term semi-myopic, providing a spectrum of methods that can improve the performance of sensing plans. In particular, we propose the efficiently computable method of ``blinkered'' VOI, and examine theoretical bounds for special cases. Empirical evaluation of ``blinkered'' VOI in the selection problem with normally distributed item values shows that is performs much better than pure myopic VOI.

In 1992, X. Zha conjectured that the line graph of a 3-connected non-planar graph contains a subdivision of $K_5$. In this talk I will present recent progress on the conjecture. (This will be the same talk as given in the DCG seminar three weeks ago).

We present an automated approach to prove termination of Java Bytecode programs by automatically transforming them to term rewrite systems (TRSs). In this way, the numerous techniques and tools developed for TRS termination can also be used for imperative object-oriented programming languages that can be compiled into Java Bytecode. Compared to direct termination analysis of imperative programs, rewrite techniques have the advantage that they are very powerful for algorithms on user-defined data structures, since they can automatically generate suitable well-founded orders comparing arbitrary forms of terms. Moreover, by using term rewriting with built-in integers, rewrite techniques are also powerful for algorithms on pre-defined data structures like integers..

In this work we study the list-decoding size of Reed-Muller codes. Given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word. We provide asymptotic bounds for the list-decoding size of Reed-Muller codes that apply to all distances. Previous results of Gopalan, Klivans and Zuckerman apply to distances only up to the minimum distance of the code.

Additionally, we study the weight distribution of Reed-Muller codes. We provide bounds for the weight distribution of Reed-Muller codes that apply to all distances. Previous results by Azumi, Kasami and Tokura apply to distances only up to 2.5 times the minimum distance of the code. Joint work with Tali Kaufman.

The talk will begin with some intro to Evolutionary Algorithms and Genetic Programming, so no related background is required.

We peruse the idea of algorithmic design through Darwinian evolution, focusing on the problem of evolving list search algorithms. Specifically, we employ genetic programming (GP) to evolve iterative algorithms for searching for a given key in an array of integers. Our judicious design of an evolutionary language renders the evolution of linear-time search algorithms easy. We then turn to the far more difficult problem of logarithmic-time search, and show that our evolutionary system successfully handles this case. Subsequently, because our setup might be perceived as being geared towards the emergence of binary search, we generalize our genomic representation, allowing evolution to assemble its own useful functions via the mechanism of automatically defined functions (ADFs). We show that our approach routinely and repeatedly evolves general and correct efficient algorithms.