^February March – 2011 ^April

Search algorithms are usually designed to return either optimal, suboptimal or any solution. In the talk I will address a different but very realistic search task: find solution with cost smaller than or equal to a given fixed constant. This task is relevant in scenarios where a fixed budget is available and we would like to find solution under the given budget with minimum search effort. For this problem, we introduced an algorithm called Potential Search (PTS) which is a best-first search that expands nodes according to the probability that they will lead to a solution whose cost is less than the given budget. Surprisingly, it is often possible to implement PTS even without explicitly calculating these probabilities, by learning the error model of the available heuristic. In addition, PTS can be modified to an anytime search algorithm. Experimental results show that PTS outperforms other relevant algorithms in most cases, and is more robust.

In the second part of the talk, I will present a novel algorithm that can predict the cost optimal solution of a given search problem. The proposed prediction algorithm builds on the CDP formula (Zahavi et. al., JAIR 2010) used to predict the number of nodes expanded in a single iteration of IDA*. Experiments on benchmark search domains show that the prediction is extremely accurate. In addition, the predicted cost can be used to enhance existing search algorithm. Experiments show that combining the prediction algorithm with Potential Search is able to find almost optimal solutions with orders of magnitude less nodes expanded when compared to A*.

Originating in statistical physics, the Abelian Sandpile Model is a diffusion process on finite graphs with a remarkably rich theory that connects the fields of algebraic graph theory, discrete dynamical systems, stochastic processes, commutative semigroups and groups, number theory, algorithms and complexity theory, and more. After a general introduction highlighting classical result by Deepak Dhar and others, I will outline recent work, in part with my former students Evelin Toumpakari and Igor Gorodezky, on the transition from "transient" to "recurrent"states in this model. I will conclude with open algorithmic problems.

This work is on the seam between differential privacy and mechanism design. We study the implementation challenge in an abstract interdependent values model and an arbitrary objective function. We design a mechanism that allows for approximate optimal implementation of insensitive objective functions in ex-post Nash equilibrium. If, furthermore, values are private then the same mechanism is strategy proof. We cast our results onto two specific models: pricing and facility location. The mechanism we design is optimal up to an additive factor of the order of magnitude of one over the square root of the number of agents and involves no utility transfers.

Underlying our mechanism is a lottery between two auxiliary mechanisms: with high probability we actuate a mechanism that reduces players' influence on the choice of the social alternative, while choosing the optimal outcome with high probability. This is where the recent notion of differential privacy is employed. With the complementary probability we actuate a mechanism that is typically far from optimal but is incentive compatible. The joint mechanism inherits the desired properties from both.

Joint work with Rann Smorodinsky and Moshe Tennenholtz.

Negotiation is a process by which interested parties confer with the aim of reaching agreements. The dissemination of technologies such as the Internet has created opportunities for computer agents to negotiate with people, despite being distributed geographically and in time. The inclusion of people presents novel problems for the design of autonomous agent negotiation strategies. People do not adhere to the optimal, monolithic strategies that can be derived analytically, as is the case in settings comprising computer agents alone. Their negotiation behavior is affected by a multitude of social and psychological factors. Furthermore, culture plays an important role in their decision making and people of varying cultures differ in the way they make offers and fulfill their commitments in negotiation. In this talk I will present the following two agents that negotiate well with people by modeling several social factors: The PURB agent that can adapt successfully to people from different cultures in complete information settings, and the SIGAL agent that learns to negotiate successfully with people in games where people can choose to reveal private information. These agents were evaluated in extensive experiments including people from three countries.

(Joint work with Y. Gal, N. Peled and G. Haim)

Trees, bushes, and other plants are ubiquitous in urban environments, and realistic models of trees can add a great deal of realism to a digital urban scene. In recent years mobile laser scanning become an efficient technology for fast acquisition of large urban scenes. Such systems generate clouds of points that are often sparse, incomplete, and noisy representation of the real scenes. In this talk I present an approach that robustly reconstructs the existing trees in a scene. This is done by a series of optimizations that construct skeletal structure and foliage for a tree based on its points.

A significant benefit of our approach is its ability to reconstruct multiple overlapping trees simultaneously without segmentation. We demonstrate the effectiveness and robustness of our approach on many raw scans of different tree varieties.

This talk is composed of two sub titles (projects): 1) Automatic Reconstruction of Tree Skeletal Structures from Point Clouds 2) Texture-Lobes for Tree Modelling

The security of various cryptosystems in common use has been completely compromised by "side channel attacks", namely, by attacks exploiting leakage of information on the underlying secret keys. Such information leakage typically emanates from physical characteristics inevitably involved in real-world implementations of cryptographic protocols (say, power consumption, timing, or electro-magnetic radiation).

In this talk I will discuss *leakage resilient cryptography* – cryptographic protocols protecting against such side channel attacks. I will focus on the _bounded memory leakage model_ (with Goldwasser and Vaikuntanathan), a model capturing a large class of side channel attacks that laid the foundations for many follow-up works on leakage resilient cryptography, and will exhibit public key encryption schemes resilient to such leakage. As time permits I will also mention extensions of these results to _unbounded memory leakage in distributed settings_ (with Goldwasser and Hazay).

The BlueGene supercomputers in production today run a small limited-function kernel called CNK (Compute-Node Kernel), which is designed to expose bare-metal performance to the application. The problem is that this comes at the expense of limiting BlueGene to only executing HPC applications, while potentially the platform can execute any type of workload. A possible solution is to replace CNK with standard Linux, but in order to get this accepted, Linux must first demonstrate performance that is comparable to CNK.

In a research conducted at the IBM T.J. Watson research center, for the first time we booted Linux on the compute-nodes of BlueGene/L and compared its performance to CNK. We identified two major obstacles to performance under Linux: the well known daemon noise problem that affects application scalability, and the high cost of TLB (Translation Lookaside Buffer) misses that affects performance at the node-level. We then leveraged unique hardware features in the system using proper software support in the Linux kernel, and demonstrated comparable performance to CNK over a wide set of HPC benchmarks.

My talk has two parts: I will begin with an introduction to supercomputing, describe the BlueGene software and hardware architecture, the structure of HPC applications, and related performance issues. I will then focus on the Linux research, present the experiments we performed, the issues we encountered, and the solutions we developed to address them.