The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v in F_2^n and a linear space L in F_2^n of dimension k NCP asks to find a point l in L that minimizes the (Hamming) distance from v. It is well-known that the nearest codeword problem is NP-hard. Therefore approximation algorithms are of interest. The best effcient approximation algorithms for the NCP to date are due to Berman and Karpinski. They are a deterministic algorithm that achieves an approximation ratio of O(k/c) for an arbitrary constant c; and a randomized algorithm that achieves an approximation ratio of O(k/ log n). In this paper we present new deterministic algorithms for approximating the NCP that improve substantially upon the earlier work, (almost) de-randomizing the randomized algorithm of Berman and Karpinski. We also initiate a study of the following Remote Point Problem (RPP). Given a linear space L in F_2^n of dimension k RPP asks to find a point v in F_2^n that is far from L. We say that an algorithm achieves a remoteness of r for the RPP if it always outputs a point v that is at least r-far from L. In this paper we present a deterministic polynomial time algorithm that achieves a remoteness of Omega(n log k / k) for all k < n/2. We motivate the remote point problem by relating it to both the nearest codeword problem and the matrix rigidity approach to circuit lower bounds in computational complexity theory.
In this paper we introduce a new technique for proving streaming lower bounds (and one-way communication lower bounds), by reductions from a problem called the Boolean Hidden Hypermatching problem (BHH). BHH is a problem that we introduce and prove the first lower bound for, but it is a generalization of a well-known problem called the Boolean Hidden Matching, that was used by Gavinsky et al. to prove separations between quantum communication complexity and one-way randomized communication complexity. The hardness of the BHH problem is inherently one-way: it is easy to solve using logarithmic two-way communication, but requires √ n communication if Alice is only allowed to send messages to Bob, and not vice-versa. This one-wayness allows us to prove lower bounds, via reductions, for streaming problems and related communication problems whose hardness is also inherently one-way. By designing reductions from BHH, we prove lower bounds for the streaming complexity of approximating the sorting by reversal distance, for approximately counting the number of cycles in a 2-regular graph, and for other problems. For example, here is one lower bound that we prove, for a cycle-counting problem: Alice gets a perfect matching EA on a set of n nodes, and Bob gets a perfect matching EB on the same set of nodes. The union EA ∪ EB is a collection of cycles, and the goal is to approximate the number of cycles in this collection. We prove that if Alice is allowed to send o ( √ n) bits to Bob (and Bob is not allowed to send anything to Alice), then the number of cycles cannot be approximated to within a factor of 1.999, even using a randomized protocol. We prove that it is not even possible to distinguish the case where all cycles are of length 4, from the case where all cycles are of length 8. This lower bound is “natively ” one-way: With 4 rounds of communication, it is easy to distinguish these two cases. 1
How can random order change the role of quantum memory in streaming? Later classical input can restore the usefulness of a quantum state consumed by earlier queries. We call this replenishment.
We construct an artificial problem based on Hidden Matching, with repeated coordinate data and online matching requests. It admits a one-pass quantum algorithm using polylogarithmic space in uniformly random order, but unconditionally requires polynomial space both classically in random order and quantumly when all updates precede the requests.
To prove the quantum lower bound, we strengthen the consumability bounds of Gilboa, Jain, and McClean for Multiple Hidden Matching. Without prior entanglement, any quantum encoding supporting r independent matching requests requires Ω(r) qubits for r≤N1/2−δ and every fixed δ∈(0,1/2), even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through r=Θ(N).
We also adapt Kallaugher's triangle-counting algorithm to uniformly random streams in which every edge is repeated equally often. Rebuilding the quantum sketch and resampling the classical estimator improve its expected-space bound in suitable parameter regimes.
Finally, we extend the robust Noisy Gap Cycle framework of Assadi and Sundaresan to quantum streaming. A quantum communication lower bound for Block Hidden XOR yields an Ω(n) space lower bound in random edge order for large enough cycles, with consequences for several graph problems.
Thus random order can enable replenishment of small quantum representations, while substantial space requirements persist for other tasks.