# Colloquium

## Cryptography and Security, Theory and Practice

This talk describes a body of research that bridges this gap, presenting two results in detal. The first is a protocol involving two parties, each one holding a private database. The aim of the protocol is to compute the well-known ID3 data-mining algorithm on the union of the databases, correctly computing the result without revealing any other information about the two databases. The result is unique in showing that an existing complex algoithm can be implemented in the style of theorists' "secure function evaluation". The protocol has sub-linear overhead, and can be applied to databses containing millions of transactions.

The second result is a Secure Human Input Protocol (SHIP), which enables human users to encrypt messages (e.g. passwords) in a way that defeats attacks by automated eavesdropping adversaries, and requires no computational aids for the users. The protocol makes novel use of several techniques that attempt to distinguish between a human user and a computer program. We give precise reductions from the security of our protocol to that of the distinguishing techniques that we use.

## Parallelizing Programs using Approximate Code

## Estimation Problems in Machine Learning

## Learning Theory and Problems of Statistics

Along with a survey of new ideas of statistical learning theory and their comparison to classical statistical approaches, I will discuss the problem of constructing learning machines that implement these new ideas.

## Automatic Tools for Building Secure Systems

## Event (no name)

## A Signal-Processing Framework for Forward and Inverse Rendering

## Programming for Pervasive Computing Environments

## Digital Voices

As any other modems, the design of these "air modems" must account for factors such as the data rate, the error probability and the computational overhead at the receiver. On top of that, these modems must also account for aesthetic and psychoacoustic factors. I will show how to vary certain parameters in standard modulation techniques such as ASK, FSK and Spread-Spectrum to obain communication systems in which the messages are musical and other familiar sounds, rather than modem sounds. Some applications of this technology will be discussed. I will also present the basis of a framework for studying low bit rate communication systems including air modems, bird songs, and human speach.

## Sparse Sampling Algorithms for Probabilistic Artificial Intelligence

Over the past several years, we have been systematically exploring the application of this fundamental notion to a broader set of natural problems in probabilistic artificial intelligence, and have found a number of striking examples where it leads to novel algorithms and analyses for core problems. In particular, by applying uniform convergence arguments to carefully structured but very sparse samples in probabilistic environments, we obtain:

* A new algorithm providing a near-optimal solution to the exploration-exploitation trade-off in Markov decision processes, a basic problem in reinforcement learning;

* A sparse sampling algorithm for planning in Markov decision processes whose running time has no dependence on the number of states;

* Powerful new algorithms for probabilistic inference in Bayesian networks:

*Algorithms for computing approximate Nash equilibria in large-population games.

These are only a few of the many algorithmic applications of learning theory methods in modern AI. This talk will present a self contained survey of these developments.