DIMACS Mixer Series, September 25, 2003

AT & T Labs


Boaz Barak, IAS

Title: Lower Bounds for Non-Black-Box Zero-Knowledge

We show several new lower bounds and impossibility results for general (i.e., non-black-box) zero-knowledge proofs and arguments. The results are that, under reasonable complexity assumptions:

1. There does not exist a constant-round zero-knowledge *strong* proof (or argument) of knowledge (as defined by Goldreich (2001)) for a nontrivial language.

2. There does not exist a two-round zero-knowledge *proof* system with perfect completeness for an NP-complete language.

The previous impossibility result for two-round zero knowledge, by Goldreich and Oren (J. Cryptology, 1994) was only for the case of *auxiliary-input* zero-knowledge proofs and arguments.

3. There does not exist a constant-round public-coin *proof* system for a nontrivial language that is *resettable* zero knowledge. This result also extends to *bounded* resettable zero knowledge.

In contrast, we show that under reasonable assumptions, there does exist such a (computationally sound) *argument* system that is bounded-resettable zero knowledge.

The complexity assumptions we use are not commonly used in cryptography. However, in all cases, we show that assumptions like ours are necessary for the above results.

Joint work with Yehuda Lindell (IBM T.J. Watson) and Salil Vadhan (Harvard).

Graham Cormode, RUTCOR, Rutgers University

Title: Simple, Fast Data Stream Summaries with Count-Min Sketches

Algorithmic work on processing massive data streams has focussed on producing efficient summaries of streams to answer particular queries. The count-min sketch answers point, range and inner product queries, and can be used as the basis of algorithms to find approximate heavy hitters and quantiles. It improves space and update time over previous solutions for dynamic data streams and the analysis is quite simple.

Alexander Soifer, DIMACS, Rutgers University

Title: The 1932 Paul Erdos' squares in a square problem & related questions

Welcome aboard. Our train of thought is about to take off. We are in Budapest, Hungary, rolled back 71 years. In 1932, the 19-year old Paul Erd?osed the following problem. Inscribe in a unit square r squares, which have no interior points in common. Denote by f(r) the maximum of the sum of side lengths of the r squares. (We allow side lengths of squares to be zero.) The problem is to evaluate the function f(r):

Open Problem 1. For every positive integer r find the value of f(r).

In fact, the above formulation came about later, when Paul and I renewed efforts to settle the problem. Originally Paul formulated the following more narrow but surprisingly difficult conjecture (that is only proven for k = 1). When Paul shared the conjecture with me in 1995, he offered a $50 price for its first proof or disproof.

Fifty Dollar Squares in a Square Conjecture (Paul Erd?1932). For any positive integer k

f(k^2 +1) = k

The conjecture is till open today, in the year 2000, waiting, as Paul Erd?sed to say, "for stronger arms, or, perhaps, brains" to be settled. But Paul and I reached a progress in a broader problem of describing the function f(r).

Martin J. Strauss, AT&T Shannon Labs

Title: Maintaining Time-Decaying Stream Aggregates

We formalize the problem of maintaining time-decaying aggregates and statistics of a data stream: the relative contribution of each data item to the aggregate is scaled down by a factor that depends on, and is non-decreasing with, elapsed time. Time-decaying aggregates are used in applications where the significance of data items decreases over time. We develop storage-efficient algorithms, and establish upper and lower bounds. Surprisingly, even though maintaining decayed aggregates have become a widely-used tool, our work seems to be the first both to explore it formally and to provide storage-efficient algorithms for important families of decay functions, including polynomial decay.

Joint work with Edith Cohen.

Anthony Ian Wirth, Princeton University
Inge Li Goertz, IT University Copenhagen (co-author)

Title: Asymmetry in k-Center Variants

This presentation will explore three concepts: the k-center problem, some of its variants, and asymmetry. The k-center problem is a fundamental clustering problem, similar to the k-median problem. Variants of \(k\)-center may more accurately model real-life problems than the original formulation. Asymmetry is a significant impediment to approximation in many graph problems, such as k-center, facility location, k-median and the TSP.

We will demonstrate an O(log* n)-approximation algorithm for the asymmetric weighted k-center problem. Here, the vertices have weights and we are given a total budget for opening centers. We will briefly discuss the Inapproximabilty of the outlier and priority variants of the asymmetric k-center problem.