^November December – 2002 ^January

Traitor tracing schemes were introduced by Chor, Fiat and Naor in 1994 in order to combat piracy in broadcast environments. In a typical piracy scenario, pirate decoders are manufactured and sold by pirates to illegal users. Traitor tracing schemes (that, in other contexts, are referred to as watermarking, frameproof, or parent-identifying codes) offer methods for fingerprinting each decoder in such a way that the fingerprint of an illegal decoder would enable the tracing of at least one of its "parents". Those schemes, however, are ineffective in dynamic piracy scenarios: As the data provider supplies access control keys to its legal users on a periodical basis, a number of these users may collude in order to publish those keys via the Internet or any other network. We introduce the concept of dynamic traitor tracing. Dynamic traitor tracing schemes rely on the feedback from the pirate network in order to modify their key allocation until they are able to incriminate and disconnect all traitors, or force them to stop their illegal activity. Those schemes are deterministic in the sense that incrimination is certain. In addition, we describe probabilistic schemes that trace all traitors with an almost certainty while imposing a small penalty on bandwidth consumption, and analyze their convergence time. Part of this work was done in collaboration with Amos Fiat.

Many classical problems (e.g. Vertex-Cover, Maximum Clique) cannot be efficiently computed unless P=NP. Thus, the next best thing would be to find an approximate solution guaranteed to be "close" to the optimum. The search for such approximation algorithms has had, in many cases, limited success. In the early 90s, an important breakthrough was achieved with the discovery of the PCP (Probabilistically Checkable Proofs) theorem. This deep theorem enabled, for the first time, proving that certain problems cannot be approximated better than a certain factor, unless P=NP. In the past decade various improvements of the PCP theorem were discovered, along with highly non-trivial ways of using it to obtain stronger (sometimes even tight) hardness of approximation results. In this talk I will give an overview of the PCP theorem and its basic connection to hardness of approximation. I will outline a central paradigm by which many of the stronger PCP hardness of approximation results have been obtained. I will introduce the "long-code" - a combinatorial object that plays a central role in these constructions, focusing in particular on vertex-cover, and hypergraph-coloring. Finally, I will touch on some of the beautiful mathematical techniques that are relied on for these constructions, including Erdos-Ko-Rado theorems on intersecting families of finite sets, influence of variables on Boolean functions, and the chromatic number of the Kneser graph. I will try to demonstrate how these seemingly unrelated objects are all really disguises of the "long-code".

Assume Alice and Bob each holds an $n$ bit number. How may they decide whose value is larger in a way that leaks no other information? This problem is well known as the Millionaires Problem - one of the first problems to be considered in the context of secure function evaluation [Yao82].

Consider any function f over the private inputs of Alice and Bob. A major plausibility result states that ``If f may be computed using polynomial resources then it may be computed securely using polynomial resources''. This result follows by a transformation from a circuit computing f to a secure protocol computing f, known as the garbled circuit transformation. However, the garbled circuit transformation usually yields very inefficient protocols, especially when compared with the non-secure version. E.g. for the Millionaires Problem it yields protocols with Omega(n) communication whereas the communication complexity of the non-secure computation is $O(poly\log n)$.

The talk will focus on two improvements on the efficiency of secure protocols. First, we will present some new transformations, that unlike the garbled circuit transformation allow for sub-linear communication complexity. As an application, we get the first sub-linear protocols for the Millionairs Problem. Then, we consider one of the basic components of secure computation - Oblivious Transfer (OT) - that usually incures most of the computation/communication costs in protocols. We will present an efficient method of extending OTs. I.e. a way of implementing a large number of OTs given just a small number of them.

We consider the problem of scheduling jobs arriving over time in a multiprocessor setting, with {em immediate dispatching}, disallowing job migration. The goal is to minimize both the total flow time (total time in the system) and the total completion time. Previous studies have shown that while preemption (interrupt a job and later continue its execution) is inherent to make a scheduling algorithm efficient, migration (continue the execution on a different machine) is not. Still, the current non-migratory online algorithms suffer from a need for a central queue of unassigned jobs which is a no option in large computing system, such as the Web. We introduce a simple online non-migratory algorithm $IMD$, which employs {em immediate dispatching}, i.e., it immediately assigns released jobs to one of the machines. We show that the performance of this algorithm is within a logarithmic factor of the optimal {em migratory offline} algorithm, with respect to the total flow time, and within a small constant factor of the optimal {em migratory offline} algorithm, with respect to the total completion time. This solves an open problem suggested by Awerbuch et al [STOC99].

Joint work with Nir Avrahami.

Abstract: A very common task in modern storage systems is to read an entire large file or a disk from beginning to end in the background while serving customer I/O requests in the foreground. Such procedures are performed during backup and restore operations, when creating temporary copies of databases or during data migrations to name a few applications. There are two different ways in which the performance of such procedures can be measured. The first concerns the negative effect of the background operation on the response time of the foreground requests. The second is the elapsed time of the background operation. Common sense indicates that improving the performance according to one measure will probably worsen the performance according to the second. Such common sense has been formalized in the famous "No free lunch theorem" of Kleinrock. Two schemes (algorithms) for managing the background operation have been studied in the past, the first by Thomasian and Menon (the TM process) and the second by Merchant and Yu (the MY process). The approximate analysis of their respective schemes via queuing theory is rather difficult. It is also difficult to analytically compare the two methods. In this talk we will first describe all the choices one has to make in order to manage a background read process, surprisingly this has not been done before. We then describe a trivial modification to both the TM and MY schemes. The modified schemes have (slightly) better performance then the original schemes in both performance measures. The analysis of performance is much simpler and it becomes easy to compare their respective performance. It turns out that the modified TM is better then the modified MY in terns of foreground response time and has the same elapsed time contradicting the common sense indications maintained above. We will take this opportunity to mention other cases, most notably from the work of Harchol-Balter and Bansal, in which the conclusions of the "No free lunch theorem" do not hold (obviously the assumptions do not hold as well).

The simplified analysis of the modified systems relies on a certain claim that the modified process requires the disk to seek very little. We will state the claim and provide an elementary proof of it (look mom, no generating functions). As it turns out we will actually be computing the size of the largest tree of a random forest, we will explain the seemingly mysterious connection via the theory of linear probing hashing, probably the oldest and most analyzed algorithm in computer science.

We shall explore a method allowing the parallel decoding of a file that has been compressed by a static Huffman code, exploiting in particular the tendency of Huffman codes to resynchronize quickly in case of an error. This will then be extended to deal with the parallel decoding of JPEG files. JPEG is a widely used standard image compression technique and the last phase of its baseline implementation includes Huffman coding. We shall assume basic knowledge of Huffman's algorithm and of the properties of Huffman codes, in particular of canonical Huffman codes, which can be found in many good textbooks. Our focus, however, is on decompression, because it may be more important than compression in some cases. For instance, in information retrieval applications, compression is done only once and may therefore be as time consuming as necessary, but decompression of short pieces is done on-line and ought to be fast to allow a reasonable response time to a query.

This is Joint work with Tomi Klein.