^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.

Alternative splicing (AS) is an RNA processing mechanism creating protein diversity in higher eukaryotes. It is regulated by splicing factors that interact with their binding sites along exons and introns. One of the main challenges in the study of AS regulation is to accurately map splicing factor binding motifs on the RNA. Therefore we developed a new method for mapping binding sites of known splicing factors which considers both the genomic environment of a single binding site and the evolutionary conservation of these sequences. The method was successfully applied to map splicing factor binding sites on specific genes and also on a wide genomic scale. By applying the algorithm on a subset of splicing factors we constructed a splicing regulatory network. This network presented a hierarchical structure that correlated with the tissue specificity levels of the splicing factors. Further to study the relationship between splicing factors and transcription regulation we derived a transcription-splicing co-regulatory network, where the nodes of the network are the Splicing Factors and the Transcription Factors (genes/proteins) and the edges represent either splicing regulation or transcription regulation. The latter network demonstrated a high level regulation between proteins involved in the gene-expression pathway, involving both splicing and transcription regulation.

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..

The talk will focus on three topics from my PhD thesis, which have applications also in other fields. The first concerns a clustering problem, in which the spatial data of objects are to be integrated with labels (e.g. features) of the objects. In the second the objects form the vertices of a graph and their labels are used to infer connections between communities of objects. The third is a new approach to statistical enrichment analysis, which takes into account degree of similarity between labels (instead of equality or non-equality). From a computational perspective the labels can be viewed (and will be presented in the talk) as colors, but the motivation for my resarch, as you all know, comes from attempts to improve the analysis of large scale data-sets of genes/gene-products.

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.