DIMACS Mixer Series - October 4, 1999

Telcordia Technologies, Morristown, NJ

1.

The Distribution Sensitive Performance of Pairing Heaps
John Iacono
Computer 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 Retrieval
Yuval Ishai
DIMACS, 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 Problems
George Karakostas
Computer Science, Princeton University

The minimum latency problem, also known as  traveling
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 the
 arrival times at 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 polynomials 
Ronitt Rubinfeld
NEC 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 Sequences
Neil J.A. Sloane
AT&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 Derandomization
Dieter van Melkebeek
DIMACS, 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).