^November December – 2005 ^January

Privacy preservation has emerged in the recent half decade as one of the more intriguing aspects of data mining. This is due to both rising concerns about rights violation using data mining and to the emergence of important markets (e.g., homeland security, cross company production chain data mining) for this type of applications. This area of research is rapidly maturing. Unfortunately, recent studies all point to one major deficiency – the lack of a well defined way of modeling the privacy retained by a privacy preserving data mining algorithm.

In this work we approach the modeling problem by extending an existing privacy model – k-anonymity – which was originally considered in the context of anonymous communication and then transfered to the context of data tables releases. We show how this model can be extended to apply to various models of a data table. Beyond its immediate contribution for the analysis of the privacy of practically any data mining model, our extension is also useful for the development of new data anonymization techniques and of new privacy preserving data mining algorithms.

Bio: Ran Wolff is a Technion CS graduate (04). He did his post-doc with distributed data mining authority Prof. Hillol Kargupta (UMBC). Previously he has been a summer intern with HP Labs Technion. In addition to peer-to-peer, grid, and sensor network data mining, Ran publishes on privacy preserving in data mining. His recent work also regards the use of data mining for grid system management. Ran has published four journal papers, numerous conference papers, and has served on the PC of major data mining conferences.

The plethora of data available nowadays has tremendous potential, but analyzing it presents a host of algorithmic challenges. Current data sets are mostly unstructured and noisy, requiring relatively complicated computational tasks, such as sequence alignment and similarity search. Furthermore, the data's enormous size might severely restrict the computational paradigm, e.g., to streaming or sublinear-time algorithms.

I will present some recent rigorous algorithmic approaches aimed at explaining and/or predicting success in practice. In particular, for problems that are hard in the worst-case, one may design a plausible model for real-life data, and then exploit this ``additional structure'' to devise improved algorithms. My running example will be near neighbor searching in regimes such as the Euclidean distance and the edit distance.

Bio: Robert Krauthgamer is a Research Staff Member at the IBM Almaden Research Center, working on the design and analysis of algorithms. Specific application areas include data analysis, combinatorial optimization, routing and peer-to-peer networks, with some recent emphasis on high-dimensional geometry and finite metric spaces.

Robert earned his PhD at the Weizmann Insitute of Science, under the supervision of Prof. Uri Feige, and after his graduation in 2001 he spent two years as a postdoc at UC Berkeley. His research won prestigious awards from the Weizmann Institute, SIAM (Society for Industrial and Applied Mathematics) and IBM Research.

We present reductions from lattice problems in the l_2 norm to the corresponding problems in other norms such as l_1, l_infty (and in fact in any other l_p norm where 1leq p leq infty ). We consider lattice problems such as the Shortest Vector Problem (SVP), Shortest Independent Vector Problem (SIVP), Closest Vector Problem (CVP) and the Closest Vector Problem with Preprocessing (CVPP). The reductions are based on embeddings of normed spaces.

Among other things, our reductions imply that the Shortest Vector Problem in the l_1 norm and the Closest Vector Problem with Preprocessing in the l_infty norm are hard to approximate to within any constant (and beyond). Previously, the former problem was known to be hard to approximate to within 2-eps, while no hardness result was known for the latter problem.

Arthur Samuel's pioneering machine learning papers are classics. Yet he is best remembered for his checkers-playing program. In 1963, his program defeated a human opponent in a single game, a milestone for the fledgling field of artificial intelligence. Since that historic encounter, checkers has been branded as a "solved" game. As a result, checkers was passed over in favor of using chess as an experimental testbed for artificial intelligence research.

The 1963 game was an aberration. In 1994, the program Chinook became the official World Man-Machine Checkers Champion, finally realizing Samuel's dream. Along the way, there was an imposing obstacle to overcome: the unbeatable human World Champion, Dr. Marion Tinsley. And thus begins our story…

Although initially begun as a research project, the Chinook effort soon changed directions and became a quest to defeat Tinsley. Instead of an impersonal contest between a man and a machine, it became a personal battle between two humans striving for supremacy at checkers. In this talk, the creator of Chinook presents the personal and technical sides of man versus machine for the World Checkers Championship.

Short Biography:

Jonathan Schaeffer is the chairman of the Department of the Computing Science, University of Alberta Edmonton, Canada. He is also the head of the "games group" of that department which are the world leaders in machine game playing research for over 20 years. He has done a considerable amount of work on games over the years and he is the creator of "Chinook" - the world champion in Checkers.

In this work we study two, seemingly unrelated, notions. Locally Decodable Codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing a multivariate polynomial and we have to determine whether the polynomial is identically zero. We improve known results on locally decodable codes and on polynomial identity testing and show a relation between the two notions. In particular we obtain the following results:

1. We prove an exponential lower bound on the length of linear LDC with 2 queries over arbitrary fields (previously it was known only for fields of size smaller than $2^n$).
2. We show that from every depth 3 arithmetic circuit C, with a bounded (constant) top fan-in that computes the zero polynomial, one can constructan LDC with 2 queries.
3. We prove a structural theorem for depth 3 arithmetic circuits, with a bounded top fan-in, that compute the zero polynomial.
4. We give new PIT algorithms for depth 3 arithmetic circuits with a bounded top fan-in.

Joint work with Zeev Dvir from the Weizmann Institute

Bio: I finished my B.Sc. in the Hebrew university in 1996. I finished my Ph.D. also at the Hebrew university in 2001. I was a post-doc at Weizmann from 2001-2 and from 2003-5. I was a post-doc in Harvard and MIT in 2002-3. As of October I am a faculty member in the Technion.

The effect of noise on computation and communication has been studied extensively in recent decades. This field of research can be traced back to Shannon, who proved that transferring information from one party to another over a noisy channel only requires a constant blowup in resource usage, compared to transmission over a noise free channel. Over the years it was shown that a constant blowup is sufficient to overcome noise for many other models

In this talk I will discuss a model introduced by El Gamal in 1984 for sharing information over a noisy broadcast network: each of N players is given one input bit, and the goal is for all players to learn (with high probability) all the input bits of the other players, using the smallest possible number of broadcasts over a joint communication channel. In each broadcast a player transmits one bit to all other players; however noise flips the bit heard by each recipient with some fixed probability.

Without noise, N broadcasts would trivially suffice for the players to learn all bits. However the best known protocol that deals with noise, discovered by Gallager in 1988, uses $N \log \log N$ broadcasts. Attempts made since to bring the blowup down to a constant have failed. Our main result is that Gallager's protocol is in fact optimal up to a constant factor

This is joint work with Navin Goyal and Michael Saks.

Short Bio:

I am currently a post-doctoral researcher with the theory group in Microsoft Research. My research is focused on theoretical computer science, and in particular in the introduction and applications of mathematical methods to computer science. I have completed my PhD in 2002 under the supervision of Prof. Shmuel Safra, and before coming to Microsoft I have been a post-doc at the Hebrew University, and in a joint two-year program of the Institute for Advanced Study in Princeton, and DIMACS (DIMACS is located at Rutgers University).

We give a general technique to obtain approximation mechanisms that are truthful in expectation. We show that for "packing domains", any alpha-approximation algorithm that also bounds the integrality gap of the LP relaxation of the problem by alpha can be used to construct an alpha-approximation mechanism that is truthful in expectation. This immediately gives a unified way of obtaining truthful mechanisms with good approximation guarantees, and yields a variety of new and significantly improved results. In particular, we obtain the first truthful mechanisms with tight approximation guarantees for a variety of multi-parameter domains: a $O(\sqrt m)$-approximation for combinatorial auctions (CAs), a $(1+\e)$-approximation for multi-unit CAs with $\Omega(\log m)$ copies of each item, and a 2-approximation for multi-parameter knapsack problems (multi-unit auctions).

Our construction is based on considering an LP relaxation of the problem and using the classic Vickrey-Clarke-Groves mechanism to obtain a truthful mechanism in this fractional domain. We show that the (fractional) optimal solution scaled down by alpha, where alpha is the integrality gap of the problem, can be represented as a convex combination of integer solutions, and by viewing this convex combination as specifying a probability distribution over integer solutions, we get a randomized, truthful in expectation mechanism. Our construction can be viewed as a way of exploiting VCG in a computationally tractable way even when the underlying social-welfare maximization problem is NP-hard.

This is joint work with Chaitanya Swamy.

An extended abstract can be downloaded from: http://www.cs.huji.ac.il/~tron/papers/mechdeslp.ps

The talk will be completely self-contained.