^November December – 2004 ^January

We study the problem of privacy preserving access to a database and in particular the problem of keyword search. In this problem records in a database are associated with keywords, and a client wishes to retrieve all records that are associated with a specific keyword. The retrieval process must hide the client's keyword from the database owner, and hide the contents of the database from the client, except for the records that are associated with the keyword.

We study various settings of this problem and give solutions based either on specific assumptions or on general primitives (mainly oblivious transfer).

Joint work with Michael Freedman, Yuval Ishai, and Omer Reingold.

Bio: Benny Pinkas received his PhD from the Weizmann Institute in 2000. Following that he worked in the research lab of Intertrust technologies, and in HP Labs (in Princeton and in Haifa). He will join Haifa University in 2005.

The game of Wythoff is a simple combinatorial game for two players. There are two piles of tokens, of sizes $x, y \ge 0$. On each turn, a player removes either any number of tokens from a single pile, or the same number of tokens from both piles. The player who takes the last token is the winner.

It turns out that the Sprague–Grundy function for this simple game behaves quite chaotically.

In this talk we will present two new results on Wythoff's Grundy function $G$. The first one is a proof that for every integer $g \ge 0$, the $g$-values of $G$ are within a bounded distance to their corresponding 0-values. Since the 0-values are located roughly along two diagonals, of slopes $\phi$ and $\phi^{-1}$, the $g$-values are contained within two strips of bounded width around those diagonals.

Our second result is a ``convergence" conjecture and an accompanying recursive algorithm. We will show that for every $g$ for which a certain conjecture is true, there exists a recursive algorithm for finding the $n$-th $g$-value in time $O(\log n)$. We will present experimental evidence in favor of our conjecture for small $g$. The talk will include a brief review of the Sprague–Grundy Theory.

Evaluating parallel job scheduling algorithms is a challenging task. Many factors affect the outcome of the evaluation, including workload and application choices, metrics, choice of scheduling algorithms and their parameters, and the hardware used or assumed. The large, non-continuous parameter space renders analytical evaluation extremely difficult, while simulation evaluations are very sensitive to the assumptions undertaken, sometimes resulting in contradicting results. Experimental evaluations are even rarer, due to the complexity of implementation, and the difficulty in obtaining a dedicated large machine for long periods of time.

This talk will describe our efforts to evaluate various scheduling strategies is a dynamic, realistic environment. Of the various parameters that affect job scheduling performance, workload and implementation play a pivotal role. Most studies either employ simulations and/or simplistic workloads, which contain many assumptions, including unknown ones. Instead, we developed a scheduling framework that implements several existing and novel algorithms on various cluster architectures of up to hundreds of nodes. This framework was used to produce the first experimental evaluation of several job scheduling strategies in a dynamic workload environment, using synthetic and scientific MPI applications. This talk will discuss the challenges involved in evaluating job scheduling strategies, and the approaches we chose to address them. An analysis will be presented of three factors affecting scheduling systems running dynamic workloads: multiprogramming level, time quantum, and the use of backfilling for queue management – and how they depend on offered load.

Joint work with Dror Feitelson (Hebrew U.), Fabrizio Petrini (LANL), and Juan Fernandez (Murcia U.)

Bio: Eitan Frachtenberg is a postdoctoral fellow at Los Alamos National Laboratory. He received his Ph.D (2003), M.Sc (2001) and B.Sc (1993) from the Hebrew University, all in computer science. His research interests include most aspects of high-performance computing, including scalable system software, job scheduling algorithms, interconnection design and protocols, cluster computing,and large-scale resource management.

A central theme in the theory of information is the stochastic study of information flow. The messages sent, the errors imposed on the network, and the request pattern of users are typically modeled as random entities, and analyzed as such. In this talk, I suggest applying notions from the field of Theoretical Computer Science to the study of Information Theory. The focus on efficiency in computation, worst case analysis, approximation algorithms,and randomization in computation (all extensively studied in the theory of computation) when addressing the field of Information Theory, raises many research directions which have both theoretical and practical interest.

In this talk I will analyze three concrete scenarios within this theme. In the area of multi party communication, I address the design of "cost efficient" codes which allow communication at capacity. Namely, combinatorial optimization in the network coding framework is considered, within which I discuss both worst case bounds on optimal costs and approximate (per instance) bounds. In the field of the design of error correcting codes for two party communication over a noisy channel, I address the well known gap between the rates achievable under the random error model (binary symmetric channel) and the Hamming error model (adversarial channel). I show that enhancing the model of two party communication by assuming that the parties involved share an extremely short secret random string allows one to close this gap. Finally, I will present relations between average and worst case analysis in algorithmic aspects of the distribution of dynamic information.

Partially based on joint work with Alexander Sprintson and Jehoshua Bruck.

Michael Langberg is a post-doc at Caltech, dept. of Computer Science.