The Quantum Black-Box Complexity of Majority

   Abstract. We describe a quantum black-box network computing the majority of N bits with zero-sided error ɛ using only

Solving Some Discrepancy Problems in NC

We show that several discrepancy-like problems can be solved in NC nearly achieving the discrepancies guaranteed by a probabilistic analysis and achievable sequentially. For example, we describe an NC algorithm that given a set system (X, S) , where X is a ground set and S⊆2 ^X , computes a set R⊆X so that for each S∈ S the discrepancy ||R S|-|R^-∩S|| is . Whereas previous NC algorithms could only achieve discrepancies with ɛ>0 , ours matches the probabilistic bound within a multiplicative factor 1+o(1) . Other problems whose NC solution we improve are lattice approximation, ɛ -approximations of range spaces with constant VC-exponent, sampling in geometric configuration spaces, approximation of integer linear programs, and edge coloring of graphs. Received June 26, 1998; revised February 18, 1999.     

Competitive Analysis of the LRFU Paging Algorithm

   Abstract. We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive ratio of LRFU is k +

Max- and Min-Neighborhood Monopolies

   Abstract. Given a graph G=(V,E) and a set of vertices M

Maintenance of a Piercing Set for Intervals with Applications

We show how to maintain efficiently a minimum piercing set for a set S of intervals on the line, under insertions and deletions to/from S. A linear-size dynamic data structure is presented, which enables us to compute a new minimum piercing set following an insertion or deletion in time O(c( S) log |S|), where c (S) is the size of the new minimum piercing set. We also show how to maintain a piercing set for S of size at most (1+?)c (S), for 0 < ? ≤ 1 , in $\bar O$ ((log |S|)/?) amortized time per update. We then apply these results to obtain efficient solutions to the following three problems: (i) the shooter location problem, (ii) computing a minimum piercing set for arcs on a circle, and (iii) dynamically maintaining a box cover for a d -dimensional point set.     

Geometric Spanners for Weighted Point Sets

Let (S,d) be a finite metric space, where each element p∈S has a non-negative weight w (p). We study spanners for the set S with respect to the following weighted distance function:

Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols

We give a deterministic algorithm which, on input an integer n , collection \cal F of subsets of {1,2,\ldots,n} , and ɛ∈ (0,1) , runs in time polynomial in n| \cal F |/ɛ and produces a \pm 1 -matrix M with n columns and m=O(log | \cal F |/ɛ ² ) rows with the following property: for any subset F ∈ \cal F , the fraction of 1's in the n -vector obtained by coordinatewise multiplication of the column vectors indexed by F is between (1-ɛ)/2 and (1+ɛ)/2 . In the case that \cal F is the set of all subsets of size at most k , k constant, this gives a polynomial time construction for a k -wise ɛ -biased sample space of size O(log n/ɛ ² ) , compared with the best previous constructions in [NN] and [AGHP] which were, respectively, O(log n/ɛ ⁴ ) and O(log ² n/ɛ ² ) . The number of rows in the construction matches the upper bound given by the probabilistic existence argument. Such constructions are of interest for derandomizing algorithms. As an application, we present a family of essentially optimal deterministic communication protocols for the problem of checking the consistency of two files. Received October 30, 1997; revised September 17, 1999, and April 17, 2000.     

Minimum Congestion Redundant Assignments to Tolerate Random Faults

Abstract. We consider the problem of computing minimum congestion, fault-tolerant, redundant assignments of messages to faulty, parallel delivery channels. In particular, we are given a set K of faulty channels, each having an integer capacity c _i and failing independently with probability f _i . We are also given a set M of messages to be delivered over K , and a fault-tolerance constraint (1-ɛ) , and we seek a redundant assignment ϕ that minimizes congestion \lilsf Cong(ϕ) , i.e. the maximum channel load, subject to the constraint that, with probability no less than (1-ɛ) , all the messages have a copy on at least one active channel. We present a polynomial-time 4-approximation algorithm for identical capacity channels and arbitrary message sizes, and a 2 \lceil\ln(|K|/\e)/\ln(1/f _max ) \rceil -approximation algorithm for related capacity channels and unit size messages. Both algorithms are based on computing a collection {K ₁ , \ldots, K _ν } of disjoint channel subsets such that, with probability no less than (1-ɛ) , at least one channel is active in each subset. The objective is to maximize the sum of the minimum subset capacities. Since the exact version of this problem is NP -complete, we provide a 2-approximation algorithm for identical capacities, and a polynomial-time (8+ \rm o (1)) -approximation algorithm for arbitrary capacities.     

Approximating Minimum Feedback Sets and Multicuts in Directed Graphs

This paper deals with approximating feedback sets in directed graphs. We consider two related problems: the weighted feedback vertex set (FVS) problem, and the weighted feedback edge set (FES) problem. In the {FVS} (resp. FES) problem, one is given a directed graph with weights (each of which is at least one) on the vertices (resp. edges), and is asked to find a subset of vertices (resp. edges) with minimum total weight that intersects every directed cycle in the graph. These problems are among the classical NP-hard problems and have many applications. We also consider a generalization of these problems: subset-fvs and subset-fes, in which the feedback set has to intersect only a subset of the directed cycles in the graph. This subset consists of all the cycles that go through a distinguished input subset of vertices and edges, denoted by X . This generalization is also NP-hard even when |X|=2 . We present approximation algorithms for the subset-fvs and subset-fes problems. The first algorithm we present achieves an approximation factor of O(log ² |X|) . The second algorithm achieves an approximation factor of O(min{log τ ^* log log τ ^* , log n log log n)} , where τ ^* is the value of the optimum fractional solution of the problem at hand, and n is the number of vertices in the graph. We also define a multicut problem in a special type of directed networks which we call circular networks, and show that the subset-fes and subset-fvs problems are equivalent to this multicut problem. Another contribution of our paper is a combinatorial algorithm that computes a (1+ɛ) approximation to the fractional optimal feedback vertex set. Computing the approximate solution is much simpler and more efficient than general linear programming methods. All of our algorithms use this approximate solution. Received May 31, 1995; revised June 11, 1996, and October 9, 1996.     

Sampling Search-Engine Results

We consider the problem of efficiently sampling Web search engine query results. In turn, using a small random sample instead of the full set of results leads to efficient approximate algorithms for several applications, such as:

Communication—Processor Tradeoffs in a Limited Resources PRAM

   Abstract. We consider a simple restriction of the PRAM model (called PPRAM), where the input is arbitrarily partitioned between a fixed set of p processors and the shared memory is restricted to m cells. This model allows for investigation of the tradeoffs/ bottlenecks with respect to the communication bandwidth (modeled by the shared memory size m ) and the number of processors p . The model is quite simple and allows the design of optimal algorithms without losing the effect of communication bottlenecks. We have focused on the PPRAM complexity of problems that have

The Quantum Complexity of Set Membership

   Abstract. We study the quantum complexity of the static set membership problem: given a subset S (|S| ≤ n ) of a universe of size m ( >> n ), store it as a table, T: {0,1} ^r --> {0,1} , of bits so that queries of the form ``Is x in S ?' can be answered. The goal is to use a small table and yet answer queries using few bit probes. This problem was considered recently by Buhrman et al. [BMRV], who showed lower and upper bounds for this problem in the classical deterministic and randomized models. In this paper we formulate this problem in the ``quantum bit probe model'. We assume that access to the table T is provided by means of a black box (oracle) unitary transform O _T that takes the basis state | y,b > to the basis state | y,b

Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness

   Abstract. We consider the quantum complexities of the following three problems: searching an ordered list, sorting an un-ordered list, and deciding whether the numbers in a list are all distinct. Letting N be the number of elements in the input list, we prove a lower bound of (1/π )(ln(N )-1) accesses to the list elements for ordered searching, a lower bound of Ω(N logN ) binary comparisons for sorting, and a lower bound of

Randomness-Efficient Sampling within NC1

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in uniform AC ⁰[⊕]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC ¹. For example, we obtain the following results:

A Randomized Linear-Work EREW PRAM Algorithm to Find a Minimum Spanning Forest

We present a randomized EREW PRAM algorithm to find a minimum spanning forest in a weighted undirected graph. On an n -vertex graph the algorithm runs in o(( log n) ^{1+ ɛ} ) expected time for any ɛ >0 and performs linear expected work. This is the first linear-work, polylog-time algorithm on the EREW PRAM for this problem. This also gives parallel algorithms that perform expected linear work on two general-purpose models of parallel computation—the QSM and the BSP.     

Small deviations for two classes of Gaussian stationary processes and <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript>-functionals, 0 < <Emphasis Type="Italic">p</Emphasis> ≤ ∞

Let w(t) be a standard Wiener process, w(0) = 0, and let η _a (t) = w(t + a) − w(t), t ≥ 0, be increments of the Wiener process, a > 0. Let Z _a (t), t ∈ [0, 2a], be a zeromean Gaussian stationary a.s. continuous process with a covariance function of the form E Z _a (t)Z _a (s) = 1/2[a − |t − s|], t, s ∈ [0, 2a]. For 0 < p < ∞, we prove results on sharp asymptotics as ɛ → 0 of the probabilities

A 3-Party Simultaneous Protocol for SUM-INDEX

Abstract. We show that the SUM-INDEX function can be computed by a 3-party simultaneous protocol in which one player sends only O(n ^ɛ ) bits and the other sends O(n ^1-C(ɛ) ) bits (0<C(ɛ)<1 ). This implies that, in the Valiant—Nisan—Wigderson approach for proving circuit lower bounds, the SUM-INDEX function is not suitable as a target function.     

Bounding the Inefficiency of Length-Restricted Prefix Codes

Abstract. We consider an alphabet Σ= {a ₁ ,\ldots,a _n } with corresponding symbol probabilities p ₁ ,\ldots,p _n . For each prefix code associated to Σ , let l _i be the length of the codeword associated to a _i . The average code length c is defined by c=\sum _i=1 ⁿ p _i l _i . An optimal prefix code for Σ is one that minimizes c . An optimal L -restricted prefix code is a prefix code that minimizes c constrained to l _i ≤ L for i=1,\ldots,n . The value of the length restriction L is an integer no smaller than \lceil log n \rceil . Let A be the average length of an optimal prefix code for Σ . Also let A _L be the average length of an optimal L -restricted prefix code for Σ . The average code length difference ɛ is defined by ɛ=A _L -A . Let ψ be the golden ratio 1.618. In this paper we show that ɛ < 1/ψ ^{L-\lceil\log (n+\lceil\log n\rceil-L)\rceil-1} when L > \lceil log n \rceil . We also prove the sharp bound ɛ < \lceil log n \rceil -1 , when L = \lceil log n \rceil . By showing the lower bound 1/(ψ ^{L-\lceil\log n\rceil+2+\lceil\log (n/(n-L))\rceil} -1) on the maximum value of ɛ , we guarantee that our bound is asymptotically tight in the range \lceil log n \rceil < L ≤ n/2 . When L\geq \lceil log n \rceil +11 , the bound guarantees that ɛ < 0.01 . From a practical point of view, this is a negligible loss of compression efficiency. Furthermore, we present an O(n) time and space 1/ψ ^{L-\lceil\log (n+\lceil\log n\rceil-L)\rceil-1} -approximative algorithm to construct L -restricted prefix codes, assuming that the given probabilities are already sorted. The results presented in this paper suggest that one can efficiently implement length restricted prefix codes, obtaining also very effective codes.     

Improved Bounds on Quantum Learning Algorithms

In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples.