DIMACS Mixer Series, October 13, 2004


Tanya Berger-Wolf, DIMACS post-doc

Title: Combinatorial models for sensor placement problems

We will discuss the topic of sensor placement in various contexts. Problems associated with placement of (environmental) sensors have been traditionally addressed using the numerical analysis toolkit. We will present a graph model of a sensor placement problem in a distribution network in several variations. Combinatorial optimization formulations of these problems are strongly related to the facility location group of problems. However, there are unique aspects of the sensor placement problem, such as identification of the source of a contamination, that make it interesting in its own right. In addition, we will point out a connection to some population sampling problems in epidemiology.

Giovanni DiCrescenzo, Telcordia

Title: Zero-Knowledge Protocols in the Public-Key Model

Zero-Knowledge protocols have received a lot of attention in the cryptographic literature, and are being studied in a variety of more and more challenging adversarial settings.

The public-key model for zero-knowledge protocols was proposed to achieve constant-round protocols for the strongest-to-date notion, called resettable zero-knowledge. In this model we can hope to obtain constant-round protocols satisfiying any of four different notions of zero-knowledge (security against a verifier trying to obtain additional knowledge other than the theorem being true) and soundness (security against a prover trying to convince the verifier of a false statement), the strongest being that of resettable zero-knowledge and resettable soundness.

As the latter was proved to be impossible to achieve, an open problem was that of achieving protocols satisfying resettable zero-knowledge and concurrent soundness. We present a recent Crypto 04 result where a concurrently sound and resettable zero-knowledge protocol for all NP languages was proposed under standard (for cryptography) intractability assumptions, enjoying the currently strongest combined security against both prover and verifier, and is applicable to settings like the Internet.

Michael L. Littman, Computer Science, Rutgers University

Title: Reinforcement Learning for Autonomous Diagnosis and Repair

This talk describes ongoing work on an application of reinforcement learning in the context of autonomous diagnosis and repair. I will present a new formal model, cost-sensitive fault remediation (CSFR), which is a simplified partially observable environment model. CSFR is powerful enough to capture some real-world problems---we've looked at network, disk-system, and web-server maintenence. However, it also admits simplified algorithms for planning, learning, and exploration, which I'll discuss.

Joint work with Nishkam Ravi at Rutgers, and Eitan M. Fenson and Richard Howard at PnP Networks, Inc.

Kah Loon Ng, DIMACS post-doc

Title: A new direction in the study of the orientation number of a graph.

For a bridgeless graph G, let D(G) be the family of strong orientations of G, and define the orientation number of G to be (G) = min{d(D) | D ? D(G)}, where d(D) is the diameter of D. An orientation of G is said to be optimal if d(D) = (G). Orientation numbers and corresponding optimal orientations of various classes of graphs have been studied extensively. In this talk, we look at a family of graphs, denoted by G, obtained when a set of edges are added to link a family of disjoint graphs. For graphs G ? G, we will look at their orientation numbers and design corresponding optimal orientations.

Sheng Zhong, DIMACS post-doc

Title: Verifiable Distributed Oblivous Transfer and Mobile Agent Security

In mobile agent computation, we consider how to protect the privacy of the agent originator against the hosts, and the privacy of each host against the originator and all other hosts. We also want to ensure that the computation task is completed correctly. Based on a previously proposed solution framework in [ACCK01], we can achieve the above goals under a threshold trust assumption. The key component of our solution is a new cryptographic primitive called Verifiable Distributed Oblivious Transfer (VDOT), which may also be of independent interest. In the design of VDOT, we use novel techniques such as consistency verification on encrypted shares and cheater identification through rerandomization. Our preliminary implementation shows that our solution can implemented efficiently.