December – 2003 ^January

The Johnson Lindenstrauss lemma states that for any n points in the Euclidean space (regardless of their initial dimension), there is a projection onto a subspace of dimension $O(\log n/epsilon^2)$ which preserves all pairwise distances to within a factor of $1+\epsilon$. In fact most projections will do, which is what makes this lemma so useful.

What happens when a faithful presentation of distances does not seem to be enough? What if we care about preserving additional geometric properties? i.e. preserving the angles between every three points? What about preserving the volumes spanned by four points, etc. ? In this work we extend the JL lemma to show that when projecting onto $k \log n \epsilon^2$ dimensions (i.e. an additional factor of $k$ compared to JL) we get that with high probability, no set of size $\le k$ changes its volume by a factor greater than $(1+\epsilon)^{k-1}$. Moreover, distances of points from affine hulls of such sets do not change by more than factor ($1+\epsilon$). A consequence of the above with $k=3$ is that angles can be preserved using the same number of dimensions as the one used in the JL lemma.

Our method can be applied to many problems with high-dimensional nature such as Projective Clustering and Approximated Nearest Affine Neighbour Search. In particular, it shows a first poly-logarithmic query time approximation algorithm to the latter.

Consider the problem of providing users with tools that enable optimal selection of configurable products, such as, vacation packages, personal computers, or even a personalized newspaper. These configuration problems can be formulated abstractly as constrained-optimization problems: Find the best (given the user?s preferences) vacation satisfying various constraints (duration, price, etc.).

This class of constrained optimization problem, which we refer to as "preference-based constrained optimization" differs from the classical constrained optimization problems studied in applied mathematics and OR. Rather than real-valued variables we are mostly dealing with discrete variables with finite domains, and instead of real-value objective functions, we have the amorphous notion of "user preferences". To formulate this class of problems properly, we need to more carefully specify their input, bearing in mind that this information must be realistically obtainable from the type of users we have in mind. We must also provide efficient solution algorithms, so that this approach is usable in on-line applications.

In this talk I will describe CP-networks, a knowledge-representation structure that exploits the notion of conditional preferential independence to enable convenient preference elicitation and representation. I will explain their basic properties and I will show how we can do preference-based constrained optimization given a CP-net efficiently. To illustrate these ideas, I will describe and demonstrate a tool we recently built for personalization of synchronized rich-media presentations

The dissection of complex biological systems is a challenging task, made difficult by the size of the underlying genetic network, the heterogeneous nature of the control mechanisms involved, and the noise inherent in the experimental data generated on such systems. In this talk I will present three strategies towards uncovering the organization of the yeast genetic network. The strategies employ novel algorithmic methods for the integrated analysis of diverse genome-wide data sources, and are readily extendable to novel experimental techniques and higher organisms.

- We applied a novel biclustering algorithm to identify groups of genes with statistically significant correlated behavior across diverse experiments. The discovered biclusters revealed a hierarchical organization of the yeast network and were used to predict the function of over 800 uncharacterized genes.

- We developed a statistical framework for identifying associations between sequence motifs that are involved in regulating gene activity. We applied this framework to sequence data from five yeast species to discover co-occurring motifs and their characteristic sequence patterns.

- We also performed a comparative study of the protein interaction networks of yeast and bacteria to identify conserved sub-networks. Our analysis was based on a detailed probabilistic model for the data, which was used to recast the question of finding conserved structures as a problem of searching for heavy subgraphs in an edge- and node-weighted graph. The discovered sub-networks shed light on evolutionary relationships between the two species.

The parallel packet switch (PPS), an extension of the inverse multiplexing architecture, is extensively used as the core of contemporary commercial switches. This talk discusses the inherent queuing delay introduced by the PPS's demultiplexing algorithm, responsible for dispatching cells to the middle-stage switches, relative to an output-queued switch. We show that the inherent queuing delay of a symmetric and fault-adaptive PPS without buffers in its input-ports is $\Omega(N)$, where N is the number of external ports. A lower-bound of $\Omega(N/S)$ is proved for an asymmetric PPS, where S is the speedup of the PPS. These lower bounds hold unless the demultiplexing algorithm has full and immediate knowledge of the switch state. Since demultiplexing algorithms with full and immediate knowledge cannot be implemented in real switches, it implies that $\Omega(N/S)$ (and sometimes even $\Omega(N)$) queuing delay is inherent in practical demultiplexing algorithms. When the PPS has buffers in its input-ports, an $\Omega(N/S)$ lower-bound holds if the demultiplexing algorithm has only local information, or the input-buffers are small relative to the time an input-port needs to learn the switch state.

This is joint work with David Hay.