DIMACS Mixer Series: featuring a program of talks by new DIMACS postdoctoral fellows and invited guests

Title:

The Geometry of Coin-Weighing Problems.

Speaker:

Noga Alon, Tel Aviv University and IAS, Princeton

Abstract:

Coin-weighing problems deal with the determination or estimation of the minimum possible number of weighings in a regular balance beam that enable one to find the required information about the weights of the coins. These questions have been among the most popular puzzles during the last fifty years. The study of some recent variants of the old puzzles is related to several seemingly unrelated topics, has an interesting geometric flavor, and combines Linear Algebra techniques with Geometric, Probabilistic and Combinatorial arguments.

Most of the new results are joint work with D. N. Kozlov and V. H. Vu.

Title:

On the knowledge complexity of NP.

Speaker:

Erez Petrank, Rutgers University

Abstract:

Knowledge complexity measures how much a party gains from an interaction with another (possibly stronger) party. Making sure that a party learns nothing or very little >from an interaction is a fundamental issue in cryptography, hence the extensive study of the special case of zero knowledge complexity. We consider Knowledge Complexity to be also a fundamental issue in complexity, where we would like to understand not only the computational abilities of machines working on their own, but also their computational abilities following an interaction with the rest of the world.

In this work, we study "what can be done" in low knowledge complexity. In particular, we ask which languages can be proven in low knowledge complexity, i.e., which languages admit interactive proofs with low knowledge complexity. We show that all languages which have interactive proofs with logarithmic knowledge complexity are in the class co-AM. This class does not contain NP unless the Polynomial Time Hierarchy (PH) collapses. Thus, if the Polynomial Time Hierarchy does not collapse, then complete NP langauges cannot be proven without yielding to the verifier super-logarithmic bits of knowledge.

This work is a joint work with Gabor Tardos.

Title:

Purely Functional Representations of Catenable Sorted Lists.

Speaker:

Haim Kaplan, AT&T Labs and Princeton University

Abstract:

We describe a new kind of finger search tree strongly related to a redundant binary representation of numbers introduced by Clancy and Knuth in 1977.

We also show how to obtain a purely functional (and hence fully persistent) implementation of our data structure without any degradation in the time bounds.

The data structure achieves logarithmic access, insertion, deletion, and split time, and double-logarithmic catenation time (these time bounds are on the worst-case). It uses one level of structural bootstrapping to obtain its efficiency.

This is joint work with Robert Tarjan.

Title:

Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound.

Speaker:

David S. Johnson, AT&T Labs

Abstract:

The Held-Karp (HK) lower bound is the solution to the linear programming relaxation of the standard integer programming formulation of the traveling salesman problem (TSP). For numbers of cities N up to 30,000 or more it can be computed exactly using the Simplex method and appropriate separation algorithms, and for N up to a million good approximations can be obtained via iterative Lagrangean relaxation techniques first suggested by Held and Karp. In this talk, we discuss these computational techniques and then consider three applications of our ability to compute/approximate the HK bound.

First, we provide empirical evidence in support of using the HK bound as a stand-in for the optimal tour length when evaluating the quality of near-optimal tours. We show that for a wide variety of randomly generated instance types the optimal tour length averages less than 0.8% over the HK bound, and even for the real-world instances in TSPLIB the gap is almost always less than 2%. Moreover, our data indicates that the HK bound can provide substantial ``variance reduction'' in experimental studies involving randomly generated instances.

Second, we estimate the expected HK bound as a function of N for a variety of random instance types, based on extensive computations. For example, for random Euclidean instances it is known that the ratio of the Held-Karp bound to sqrt N approaches a constant C_HK, and we estimate both that constant and the rate of convergence to it.

Finally, we combine this information with our earlier results on expected HK gaps to obtain estimates for expected optimal tour lengths. For random Euclidean instances, we conclude that C_OPT, the limiting ratio of the optimal tour length to sqrt N, is .7124 +- .0002, thus invalidating the commonly cited estimates of .749 and .765 and undermining many claims of good heuristic performance based on those estimates. For random distance matrices, the expected optimal tour length appears to be about 2.042, adding support to a conjecture of Krauth and Mezard.

This work was done in collaboration with Lyle McGeoch of Amherst College and Ed Rothberg of Silicon Graphics.

Title:

"Several Problems Related to the Erdos-Szekeres Theorem."

Speaker:

Pavel Valtr, Rutgers University

Abstract:

The Erdos-Szekeres k-gon Theorem says that for any integer k there is an integer n(k) such that any set of n(k) points in the plane, no three on a line, contains k points which are vertices of a convex k-gon. In the talk we will discuss various problems and results related to the Erdos-Szekeres Theorem. 

 Program 

    8:45              Coffee


    9:00 -  9:05      Fred Roberts
                      DIMACS Director, Rutgers University
                      Opening Remarks.

    9:05 -  9:55      Noga Alon
                      Tel Aviv University and 
                      Discrete Probability Visitor at IAS
                      "The Geometry of Coin-Weighing Problems."

    9:55 - 10:20      Erez Petrank
                      Rutgers University
                      "On the Knowledge Complexity of NP."


   10:20 - 10:35      Coffee Break


   10:35 - 11:00      Haim Kaplan
                      AT&T and Princeton University
                      "Purely Functional Representations of 
                        Catenable Sorted Lists."

   11:00 - 11:25      Pavel Valtr
                      Rutgers University
                      "Several Problems Related to the Erdos-Szekeres
                        Theorem."

   11:25 - 12:15      David Johnson
                      Networks Special Year Chair, AT&T
                      "Asymptotic Experimental Analysis for the
                        Held-Karp Traveling Salesman Bound."

      Lunch
Document last modified on September 4, 1996