# Chapter 19: Theory

## Bounding Congestion in Networks

Chris Harrelson and Kirsten Hildrum
(Professor Satish Rao)

A recent result by Harald Räcke [1] gives an oblivious algorithm for routing a flow in a general graph G=(V,E) with polylogarithmic (in V) congestion over the optimal set of routes. He does this by showing there exists an embedding of any graph into a tree, T(G), and that routing any flow on T(G) is no worse than routing the same flow on G. In addition, he also embeds T(G) on to G and shows that it is possible to route on G with only polylogarithmically more congestion than on T(G). Räcke, however, does not give a polynomial-time algorithm for constructing the embedding.

We have several goals related to this. First, we seek to give a polynomial-time construction of an embedding that can be used this way, and hope that such a construction will give lead to a simpler proof of his result.

Second, we wish to find, in general, the cost of an oblivious algorithm. While Räcke's result shows that the gap between the best oblivious algorithm and the best non-oblivious algorithm is polylog(n) for the general case, this may not be tight, and the gap may even be constant when all the messages have a single source or single destination. The gap may be larger if the graph is allowed to have directed edges.

[1]
H. Räcke, "Minimizing Congestion in General Networks," Proc. Symp. Foundations of Computer Science, Vancouver, Canada, November 2002.

Send mail to the author : (hildrum@eecs.berkeley.edu)

## Finding the Nearest Neighbor Using Queries to a Distance Oracle

Kirsten Hildrum
(Professor Satish Rao)

Given a set of points, S, in a metric space and query point q, the goal is to find the point in S closest to q. Ideally, the data structure to do this only relies on an oracle that gives the distance between any two points, and not on any other detail of the metric space.

In some metric spaces, this seems difficult. Consider, for example, a metric space and a query point such that all points in S are at a distance one from each other, and all but one are at distance q from S. Finding the one point closest to q will probably require querying the distance from q to every point in S. In other metric spaces, it is possible to do this with a logarithmic number of queries (see [1] or [2]).

Following up on [1] and [2], we have a result showing that this can be done in constant space and logarithmic time for unchanging sets S and hope to argue that a similar data structure with expected constant space works for dynamic sets S.

A more general goal is to characterize the metric spaces for which finding the nearest point requires a sublinear number of queries and develop algorithms for those metric spaces.

[1]
K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao, "Distributed Object Location in a Dynamic Network," Proc. ACM Symp. Parallel Algorithms and Architectures, Winnepeg, Canada, August 2002.
[2]
D. Karger and M. Ruhl, "Finding Nearest Neighbors in Growth-Restricted Metrics," Proc. ACM Symp. Theory of Computing, Montreal, Canada, May 2002.

Send mail to the author : (hildrum@eecs.berkeley.edu)

## Quantum Lower Bound for the Collision Problem

Scott Aaronson
(Professor Umesh Vazirani)
DARPA grant and NSF Graduate Fellowship

The collision problem is to decide whether a function X:{1,..,n}->{1,..,n} is one-to-one or two-to-one, given that one of these is the case. We show a lower bound of Ω(n1/5) on the number of queries needed by a quantum computer to solve this problem with bounded error probability. The best known upper bound is O(n1/3), but obtaining any lower bound better than Ω(1) was an open problem since 1997. Our proof uses the polynomial method augmented by some new ideas. We also give a lower bound of Ω(n1/7) for the problem of deciding whether two sets are equal or disjoint on a constant fraction of elements. Finally we give implications of these results for quantum complexity theory.

[1]
S. Aaronson, "Quantum Lower Bound for the Collision Problem," Proc. ACM Proc. ACM Symp. Theory of Computing, Montreal, Canada, May 2002.

Send mail to the author : (aaronson@cs.berkeley.edu)

## The Complexity of Recursive Fourier Sampling

Scott Aaronson
(Professor Umesh Vazirani)

In recent work we are revisiting the oft-neglected recursive Fourier sampling (RFS) problem, introduced by Bernstein and Vazirani [1] to prove an oracle separation between BPP and BQP. RFS seems to offer the best hope for proving that BQP is not in the polynomial hierarchy relative to an oracle. As a first step, we seek to place RFS outside a smaller complexity class such as AM or Σ2P relative to an oracle.

In previous work [2], one of us showed that the known quantum algorithm for RFS is essentially optimal, despite its seemingly wasteful need to uncompute information. This implies that, to place BQP outside of PH[log] relative to an oracle, one would need to go outside the RFS framework. Our proof argues that, given any variant of RFS, either the adversary method of Ambainis [3] yields a good quantum lower bound, or else there is an efficient classical algorithm. This technique may be of independent interest.

[1]
E. Bernstein and U. Vazirani, "Quantum Complexity Theory," SIAM Journal on Computing, Vol. 26, No. 5, 1997.
[2]
S. Aaronson, "Quantum Lower Bound for Recursive Fourier Sampling" (submitted).
[3]
A. Ambainis, "Quantum Lower Bounds by Quantum Arguments," Journal of Computer and System Sciences, Vol. 64, 2002.