March – 2004 ^April

Complex biological systems containing tissue immersed in a viscous incompressible fluid are ubiquitous. Understanding the dynamics of such systems is crucial in a vast array of scientific and engineering problems, such as the function of the heart, the mechanism of hearing, the dynamics of biological membranes, cell morphology and insect flight, to name a few. In such systems the tissue may be elastic or active, and it may posess complicated internal structure. Its interaction with the fluid is often coupled with other physical processes, such as biochemical reactions, electrical currents and heat diffusion.

In this talk I will survey my work on large-scale computer modeling of such systems using the immersed boundary method. I will discuss the application of this work to modeling the fluid dynamics of the heart and (in more detail) the construction of a computational model of the cochlea (the inner ear).

This is the first of 2-3 lectures in which we relate the asymptotics of the first rows in a partition via representation thoery to some special coverings of the sphere by Riemann surfaces. The lecture is independent of last week's lecture.

In the late nineties Erickson proved a remarkable lower bound on the decision tree complexity of one of the central problems of computational geometry: given $n$ numbers, do any $r$ of them add up to $0$? His lower bound of $\Omega(n^{\lceil r/2\rceil})$, for any fixed $r$, is optimal if the polynomials at the nodes are linear and at most $r$-variate.

We generalize his bound to $s$-variate polynomials for $s>r$. Erickson's bound decays quickly as $r$ grows and never reaches above pseudo-polynomial: we provide an exponential improvement.

Our arguments are based on three ideas:

(i) a geometrization of Erickson's proof technique;

(ii) the use of error-correcting codes; and

(iii) a tensor product construction for permutation matrices.

We introduce several on-line multidimensional bin packing models and discuss the unique properties of each one of them. Then we concentrate on the oriented bounded space model and describe the results in more detail. For this model we present an algorithm of tight asymptotic performance ratio both for the general case of hyperbox packing, and the more special case of hypercube packing. This ratio is exponential in the dimension for hyperboxes, but sub-linear for hypercubes.

Most results presented in this talk are based on a joint work with Rob van Stee.

Compugen focuses on developing processes that yield discoveries with a high probability of successfully making it into clinical development and onwards. Those processes combine "Dry" approaches based on mathematical and computational models with more traditional "Wet" laboratory processes. A key element in the success of these processes is a rapid cycle of development, verification and improvements, driven by closely knit groups of biologists and algorithm developers.

In this presentation, we will review the structure and components of those processes, and provide examples of a ctual discoveries achieved through their operation. We will focus on the processes that are at the heart of Compugen's current discovery efforts: platforms to create an accurate genomic infrastructure and discovery engines targeted at therapeutic proteins and biomarkers.