Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition

• The paper gives algorithms and tight upper and lower bounds for recognizing PQ, STACK, and DEQUE as passive operation-transcript languages.The checker observes operations rather than modifying inserted items or adding read operations.Source: §1 · pp. 2–3
• The information-cost tradeoff is needed for direct-sum lower bounds, but the required version must account for Bob seeing Alice’s prefix and receiving a check bit.The check bit makes the easy-distribution information-cost analysis materially different.Source: §1 · p. 2
• With two-sided error at most 1/ log2 n, either Alice reveals Ω(n) information or Bob reveals Ω(1) under the easy distribution.This tradeoff applies to randomized AUGMENTED-INDEX protocols.Source: §1 · p. 2
• A direct-sum theorem and reduction from MULTI-AI yield multi-pass lower bounds for DYCK(2), separating unidirectional passes from two opposite-direction passes.Magniez et al. give an O(log^2 N)-space algorithm with two passes in opposite directions, while multiple unidirectional passes are exponentially harder.Source: §1 · pp. 2–3
• The proof addresses input sharing, which breaks the rectangle property, through a weakened rectangle property and the Fat Transcript Lemma’s interplay with information cost.The paper identifies this as its main technical hurdle.Source: §1 · p. 4

2 Augmented Index and an Information Cost Tradeoff

• The information costs condition on the public random string and are bounded above by the respective players’ communicated bits.The passage notes that conditioning on public randomness is crucial; without it, the costs can be zero.Source: §2 · p. 4
• The proof uses an easy distribution obtained by conditioning the uniform input distribution on X_K = C.On this conditioned distribution, the AUGMENTED-INDEX output is zero with probability one.Source: §2 · p. 4
• The main theorem gives an information-cost lower bound for low-error AUGMENTED-INDEX protocols under the stated input distribution.The proof concludes that the four conditions on a transcript cannot hold together.Source: §2 · pp. 5–6
• Because Bob knows Alice’s length-(k−1) prefix, transcript distributions need only satisfy a weaker factorization than the usual rectangle property.The proof uses this weaker property to handle the input sharing in AUGMENTED-INDEX.Source: §2 · p. 6
• The Fat Transcript Lemma rules out a transcript that simultaneously has the specified entropy and accuracy properties.The proof selects a transcript with those properties by averaging, then derives a contradiction.Source: §2 · pp. 6–7

3 A Direct Sum Argument

• MULTI-AI asks the players to compute the conjunction of m AUGMENTED-INDEX predicates across p rounds of private messages.The players follow the stated forward-and-reverse sequence, with A1 announcing the answer.Source: §3 · p. 9
• Every [p, s, 1/log^2 n]-protocol for MULTI-AI_m,n satisfies ps = Ω(min{m, n}).The section describes this bound as near-optimal, with one-round protocols achieving s = O(n) or s = O(m log n).Source: §3 · p. 9
• The lower bound formalizes the intuition that solving m independent instances requires communication that scales with the number of instances.The proof uses a refinement of the information-complexity paradigm.Source: §3 · p. 9
• The direct-sum theorem converts a MULTI-AI protocol into a single-instance AI protocol while relating its information cost to the multi-instance cost.The reduction uses Alice communication at most ps bits and the product easy distribution µ0^⊗m.Source: §3 · p. 9

4 Streaming Language Recognition and Passive Memory Checking

• An O(log N)-space stream reduction maps DYCK(2) to PQ(4N), linking recognition of balanced two-type parentheses to priority-queue transcript checking.Source: §4 · p. 10
• Theorem 4.4 gives p-pass space lower bounds for DYCK(2) and PQ(N), resolving the conjecture of Magniez et al. [15].Source: §4 · p. 10
• DYCK(2) admits two opposite-direction passes in O(log^2 N) space, while polylog-space unidirectional algorithms require eΩ(N) passes, separating the models.Source: §4 · p. 10

4.1 Passive Checking of Priority Queues

• PQ-CHECK recognizes priority-queue transcripts in one pass using O(N(log U + log N)) bits, accepting valid inputs with certainty and rejecting invalid ones with probability at least 1 − 1/N^2.Its X, Y, and Z arrays track per-item, per-epoch counts and maximum balance to detect invalid operation order.Source: §4.1 · pp. 11–12
• A priority-queue checker tracks unmatched items and the greatest extracted item to detect local-consistency violations, using O(|σ′| log |σ′|) time and O(|σ′|) space.The checker uses priority queues for its item multisets; its space-efficient PQ-CHECK implementation uses linear hashes as fingerprints.Source: §4.1 · p. 15

4.2 Passive Checking of Stacks, Queues, and Deques

• STACK can be recognized in one pass using O(N log N) bits of space with high probability.The theorem fragments state a lower-bound result too, but do not provide enough of its expression to report it.Source: §4.2 · p. 15
• QUEUE can be recognized in one pass using O(log N) space by fingerprinting whether each insertion’s value matches the corresponding extraction’s value [5].Source: §4.2 · p. 16
• DEQUE can be recognized in one pass using O(N log N) bits of space with high probability.Its checker stores hashes of item-and-height pairs in a deque, applying extractions at the corresponding end and rejecting nonzero hashes that should represent no items.Source: §4.2 · p. 16

4.3 Variations with timestamps

• Timestamped stacks, queues, and deques can be verified in O(log N) space, but the complexity of timestamped priority-queue recognition remains open because the augmented-indexing reduction no longer applies.The timestamped variants require each timestamp to appear at most once across extracts and to match its insertion.Source: §4.3 · pp. 16–17

• For public-coin protocols, Alice’s portion of the transcript carries exactly the information about her input given Bob’s input and the public randomness; the analogous identity holds for Bob.The lemma states I(T : X | Y, R) = I(A : X | Y, R) and I(T : Y | X, R) = I(B : Y | X, R).Source: A Proof of the Direct Sum Theorem · p. 18
• A [p, s, ε]-protocol for MULTI-AI_m,n yields an ε-error protocol for AI_n in which Alice sends at most ps bits.The theorem statement also asserts an information-cost condition, but its bound is not included in the supplied passage.Source: A Proof of the Direct Sum Theorem · p. 18
• The simulation embeds Alice’s and Bob’s AI inputs at coordinate j, generates the other coordinates, then jointly simulates Q on the resulting MULTI-AI input.The other coordinates are generated so their inputs follow μ0; the players simulate Q round by round.Source: A Proof of the Direct Sum Theorem · p. 18
• Because every coordinate except j has AI output 0 under μ0, the simulated MULTI-AI output equals the embedded AI output, preserving Q’s error bound.The constructed protocol has worst-case error at most ε whenever Q is correct with error ε.Source: A Proof of the Direct Sum Theorem · p. 19

• There exists an O(log N)-space stream reduction from DYCK(2) to PQ(4N).Source: B Reduction from DYCK(2) to PQ · p. 19
• The map ψ uses prefix height to choose inserts or extracts and their keys, assigning distinct key offsets to the two parenthesis types.The construction defines height as opens minus closes and uses the preceding or current prefix height to select each operation’s key.Source: B Reduction from DYCK(2) to PQ · p. 19
• The transformation can be computed in O(log N) space by maintaining the heights of the last two elements.The passage also states that the transformation is onto [4N].Source: B Reduction from DYCK(2) to PQ · p. 20
• If p is in DYCK(2), induction on its length establishes that ψ(p) is a valid priority-queue sequence.The proof decomposes the string around a matching pair and uses the induction hypothesis on the remaining Dyck string.Source: B Reduction from DYCK(2) to PQ · p. 20
• If p is not in DYCK(2), unequal numbers of opens and closes or a negative prefix height make ψ(p) invalid for PQ.The proof also analyzes a minimal prefix pattern where the two parenthesis types mismatch.Source: B Reduction from DYCK(2) to PQ · p. 20