Most of the new results are joint work with D. N. Kozlov and V. H. Vu.
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.
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.
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.
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