For the above-named work, a missing sentence that should have been included in the first footnote is provided.

This paper proposes a low-complexity and high-throughput decoder (D_LBAC) based on Logarithmic Binary Arithmetic Coding (LBAC). The proposed D_LBAC has high throughput and low complexity. It does not use multiplication and division operations nor look up tables (LUTs). The proposed D_LBAC is a simple algorithm structure and only requires additions and shift operations. Experimental results show it can decode 3.5 symbols per cycle on average. The hardware implementation design described in this paper can achieve the high symbol processing capability and the low hardware costs.

This paper proposes a new efficient bypass coding scheme (EBCS) based on Logarithmic Binary Arithmetic Coding (LBAC). The bypass coding model is used to encode a symbol which has equal probability (0.5). The percentage of the bypass coding model is about 25 in CABAC of H.265/HEVC. The proposed EBCS provides a hardware-efficient design that can significantly increase the processing speed, and it has a simple algorithm structure. Experimental results show that the EBCS can reduce bypass coding time by 60% roughly. For a hardware implementation in this paper, the overall processing speed is improved by about 96%, and the hardware cost is low.

This paper proposes an efficient adaptive binary arithmetic coder based on a logarithmic domain (LBAC) and a probability estimation based on the LBAC (P-LBAC). Both the LBAC and the P-LBAC achieve a high data-compression ratio with low complexity and a hardware-efficient structure. They introduce a mapping mechanism between the logarithmic domain and the original domain for both the coding process and the probability estimation. The proposed schemes have high accuracy and constitute an efficient BAC. The proposed LBAC and P-LBAC do not use either multiplication and division operations or lookup tables, and only addition and shifting operations are required. The proposed LBAC is designed to favor the coding of multiple symbols and has high throughput. The proposed P-LBAC achieves a good tradeoff between accuracy and speed in probability estimation through a single parameter. When the proposed algorithms are implemented on H.265/HEVC platforms, and they achieve a compression efficiency equivalent to that of CABAC.

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 generalization of the well-known Boolean Hidden Matching problem, which was used by Gavinsky et al. to prove an exponential separation between quantum communication complexity and one-way randomized communication complexity. We are the first to introduce BHH, and to prove a lower bound for it. The hardness of the BHH problem is inherently one-way: it is easy to solve BHH using logarithmic two-way communication, but it 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, of approximately counting the number of cycles in a 2-regular graph, and of 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.

Thorup and Zwick, in their seminal work, introduced the approximate distance oracle, which is a data structure that answers distance queries in a graph. For any integer k, they showed an efficient algorithm to construct an approximate distance oracle using space O(kn1+1/k) that can answer queries in time O(k) with a distance estimate that is at most ¿ = 2k-1 times larger than the actual shortest distance (this ratio is called the stretch).They proved that, under a combinatorial conjecture, their data structure is optimal in terms of space: if a stretch of at most 2k-1 is desired, then the space complexity is at least n1+1/k. Their proof holds even if infinite query time is allowed: it is essentially an "incompressibility" result. Also, the proof only holds for dense graphs, and the best bound it can prove only implies that the size of the data structure is lower bounded by the number of edges of the graph. Naturally, the following question arises: what happens for sparse graphs? In this paper we give a new lower bound for approximate distance oracles in the cell-probe model. This lower bound holds even for sparse (polylog(n)-degree) graphs, and it is not an "incompressibility" bound: we prove a three-way tradeoff between space, stretch, and query time. We show that when the query time is t and the stretch is ¿, then the space S must be S ¿ n1+¿(1/t¿)/lg n. This lower bound follows by a reduction from lopsided set disjointness to distance oracles, based on and motivated by recent work of Patrascu. Our results in fact show that for any high-girth regular graph, an approximate distance oracle that supports efficient queries for all subgraphs of G must obey this tradeoff. We also prove some lemmas that count sets of paths in high-girth regular graphs and high-girth regular expanders, which might be of independent interest.