1. The Distribution Sensitive Performance of Pairing HeapsDocument last modified on September 8, 1999.John IaconoComputer Science Department, Rutgers University, Piscataway, NJ Pairing heaps are a self adjusting form of heap which are closely related to splay trees. They are easy to implement and empirically perform well. They are in widespread use, appearing in the GNU C++ Library, and in introductory undergraduate texts. It will be shown that pairing heaps exhibit a kind of distribution sensitive performance, similar to that which splay trees are well known for. Specifically, results will be presented that prove that pairing heaps support extract-min operations in amortized time $O(\log k)$, where $k$ is the maximum number of items smaller than the item to be removed that were ever in the heap concurrently with the item to be removed. An application of this result will then be presented: Given a set of ordered lists of varying lengths, pairing heaps can be used to merge the lists optimally, within a constant factor. 2. Improved Upper Bounds on Information-Theoretic Private Information RetrievalYuval IshaiDIMACS, Rutgers University Private information retrieval (PIR) schemes allow a user to retrieve the i-th bit of an n-bit database x, replicated in k servers, while keeping the value of i private from each server. A {\em t-private} PIR scheme protects the user's privacy from any collusion of up to t servers. The main cost measure for such schemes is their communication complexity. The talk will introduce a new approach for the construction of information-theoretic (i.e., unconditionally secure) PIR schemes, resulting in improved and simplified upper bounds on the communication complexity of PIR. The talk is based on a joint work with Eyal Kushilevitz. 3. Approximation Schemes for Minimum Latency ProblemsGeorge KarakostasComputer Science, Princeton University Theminimum latency problem, also known astraveling repairman problem, is a variant of the TSP in which the starting node of the tour is given and the goal is to minimize the sum of thearrival timesat the other nodes. We present a quasipolynomial-time approximation scheme for this problem when the instance is a weighted tree and when the the nodes lie in $\Re^d$ for some fixed $d$. The best polynomial time approximation algorithm due to Goemans and Kleinberg, computes a 3.59... approximation. 4. Understanding noisy data: the case of polynomialsRonitt RubinfeldNEC Research Institute In this survey talk, we focus on the following problem and natural variants of it: Given a set of values $ T = (x_1,f(x_1)),...,(x_n,f(x_n))$ a parameter $\delta$ and an integer $d$, find a degree $d$ polynomial $p$ such that $p$ and $f$ agree on at least a $\delta$ fraction of the inputs in $T$. This problem has a wide range of applications, including several in coding theory, complexity theory, and cryptography. When $\delta=1$, this is just the problem of polynomial interpolation. The problem was solved by Berlekamp and Welsh in the univariate case when $\delta >1/2$ and $n$ is large compared to $d$. Until recently, this seemed to be a natural barrier since when $\delta < 1/2$ and $n$ is large compared to $d$, there may be more than one polynomial which agrees on a $\delta$ fraction of $T$. However, it turns out that the problem can be solved even when $\delta < 1/2$. We survey the recent advances on this problem and their applications. 5. The Online Encyclopedia of Integer SequencesNeil J.A. SloaneAT&T Shannon Lab, Florham Park, NJ An overview of this project profusely illustrated with examples of wonderful sequences. Several open problems will be mentioned. 6. Graph Isomorphism and DerandomizationDieter van MelkebeekDIMACS, Rutgers University, Piscataway, NJ Graph isomorphism is one of the few candidate NP-problems believed to be neither in P nor NP-complete. One of the reasons why complexity theorists believe it not to be NP-complete is the structure of the complement: Graph nonisomorphism seems easier than the complement of any known NP-complete language. A crucial open question in this context is whether, for any pair of nonisomorphic graphs, one can give a short proof that there exists no isomorphism between them. The shortest known proofs for graph nonisomorphism are of exponential size. We provide strong evidence that one can do better: Under the assumption that the polynomial-time hierarchy does not collapse, we will exhibit subexponential size proofs. Under a stronger assumption we are able to reduce the proof size to polynomial. We obtain our results by derandomizing a randomized proof system for graph nonisomorphism known as an Arthur-Merlin game. Our derandomization technique works for any Arthur-Merlin game, as well as for several other randomized processes. In particular, it applies to constructing universal traversal sequences, nonadaptively finding witnesses for NP-problems, learning Boolean circuits, and building rigid matrices. This is joint work with Adam Klivans (MIT).