^October November – 2004 ^December

We will describe definitions and algorithmic results for the ``census problem''. Informally, in a census individual respondents give private information to a trusted (and trustworthy) party, who publishes a sanitized version of the data. There are two fundamentally conflicting requirements: privacy for the respondents and utility of the sanitized data. Unlike in the study of secure function evaluation, in which privacy is preserved to the extent possible given a specific functionality goal, in the census problem privacy is paramount; intuitively, things that cannot be learned ``safely'' should not be learned at all.

The definition of privacy and the requirements for a safe sanitization are important contributions of this work. Our definition of privacy formalizes the notion of protection from being brought to the attention of others – one's privacy is maintained to the extent that one blends in with the crowd. Our definition of a safe sanitization emulates the definition of semantic security for a cryptosystem and says, roughly, that an adversary given access to the sanitized data is not much more able to compromise privacy than an adversary who is not given access to the sanitization.

Joint work with Shuchi Chawla, Cynthia Dwork, Frank McSherry, and Hoeteck Wee.

A preliminary version of the paper is available from : http://theory.lcs.mit.edu/~asmith/

In this talk I will describe (briefly) what the PCP theorem is, and then describe recent work in which we look back into the proof of the PCP theorem, with the goal of finding new proofs that are "more combinatorial" and arguably simpler. For that we introduce the notion of assignment tester. This natural object is a strengthening of the standard PCP verifier, and enables simpler composition that is truly modular (i.e. one can compose two testers without any assumptions on how they are constructed). A related notion was independently introduced by Ben-Sasson et. al. Based on this notion, we present two main results:

1. The first is a new proof of the PCP theorem. This proof relies on a rather weak PCP given as a "black box". From this, we construct combinatorially the full PCP, relying on composition and a new combinatorial aggregation technique.

2. Our second construction is a "standalone" combinatorial construction showing NP in PCP [polylog, 1]. This implies, for example, that max-SAT is quasi-NP-hard

Based on joint work with Omer Reingold.

We introduce a fast, Multiscale algorithm for clustering, based on a fast segmentation algorithm introduced by Sharon, Brandt and Basri (Sharon et al., 2000).

It finds an approximate solution to normalized cut measures in a weighted graph, in a time that is linear in the number of edges in the graph, and yields a hierarchical decomposition of the graph into clusters at all scales. The algorithm detects the clusters by applying a process of recursive coarsening in which the same minimization problem is represented with fewer and fewer variables producing an irregular pyramid. Each node in the pyramid represents an aggregate of fine nodes, thus the pyramid yields the complete hierarchy of clusters at all scales. The coarsening procedure yields an easy platform to compute additional internal statistics of the emerging intermediate level clusters. These additional measurements are used during the aggregation, and also in a top-down manner in the higher level clustering.

In this talk I will present the algorithm, as well as show its capabilities on real data from computer vision, graphics, and biology.

Joint work with Eitan Sharon, Meirav Galun and Achi Brandt

Heuristic Search in Artificial Intelligence is a general mechanism for path finding and for solving exponential combinatorial problems (e.g., Chess, Rubik's Cube etc,) with the usage of intelligent heuristics. An efficient way to speed up the search is to use a more accurate heuristic function. In the talk we will cover some of the recent developments in creating accurate heuristics. We will also cover the new trend in this field is to effectively apply heuristic search to problems from other areas of computer science such as vertex-cover, graph-partitioning etc,

In particular, we will discuss "Pattern-database heuristics" which are a recent breakthrough that have made a revolution in calculating accurate heuristic functions. Pattern databases are large tables that store solutions to "patterns" or subproblems in the computer's memory. These solutions are then used as heuristics that guide the search. With pattern databases we are able to solve problems thousands of times faster than with previous heuristics.

We will present the basics of pattern databases and then show how to enhance pattern databases by a number of methods such as, compressing large pattern databases into a small amount of memory, use multiple pattern databases, learn pattern databases with neural networks etc, Experimental results of the different methods on a number of domains will be provided.

More information on search can be found in: http://www.ise.bgu.ac.il/faculty/felner/

Wireless ad hoc radio networks have gained a lot of attention in recent years. We consider geometric networks, where nodes are located in a euclidean plane. We assume that each node has a variable transmission range and can learn the distance to the closest neighbor. We also assume that nodes have a special collision detection (CD) capability so that a transmitting node can detect a collision within its transmission range. We study the basic communication problem of collecting data from all nodes called convergecast. Recently, there appeared many new applications such as real-time multimedia, battlefield communications and rescue operations that impose stringent delay requirements on the convergecast time. We measure the latency of convergecast, that is the number of time steps needed to collect the data in any n-node network. We propose a very simple randomized distributed algorithm that has the expected running time O(log n). We also show that this bound is tight and any algorithm needs $\Omega(log n)$ time steps while performing convergecast in an arbitrary network.

One of the most important problems in wireless ad hoc networks is to minimize the energy consumption, which maximizes the network lifetime. We study the trade-off between the energy and the latency of convergecast. We show that our algorithm consumes at most $O(n \log n)$ times the minimum energy. We also demonstrate that for a line topology the minimum energy convergecast takes $n-1$ time steps while any algorithm performing convergecast within $O(\log n)$ time steps requires $\Omega(n)$ times the minimum energy.

Joint work with Dariusz Kowalski.