INTRODUCTION

One of the gems in Shannon's famous 1948 paper introducing information theory [17] is the channel capacity formula, that gives the maximum rate possible for an error correcting code over any discrete memoryless channel. Recall that an error correcting code with rate 𝑟 allows one party to reliably communicate a message consisting of 𝑛 symbols to a remote second party, with a negligible probability of error, by sending only 𝑛 • (1/𝑟 + 𝑜 (1)) symbols over the channel. Let C Γ,𝜖 be the symmetric channel with alphabet set Γ and noise rate 𝜖. 1 The channel capacity formula shows that the maximum rate over C Γ,𝜖 approaches 1 as the noise rate 𝜖 approaches 0. For instance, the maximum rate over C {0,1},𝜖 is 1 -H(𝜖), where H is the binary entropy function.

Schulman's groundbreaking work [15] studied error correcting codes in the łtwo-wayž setting, where there are noisy channels between the two communicating parties in both directions. Such error correcting codes are called interactive codes and they allow the encoding of interactive protocols, which may consist of many backand-forth messages, in a noise-resilient way. Following Schulman's question regarding the maximum rate of interactive codes [15], Kol and Raz [12] defined the notion of interactive channel capacity, which is the analogue of channel capacity in the interactive setting. For every 𝜖 > 0, they designed an interactive code with rate 𝑟 𝜖 = 1 -O ( √︁ H(𝜖)) over the two-way binary symmetric channel, under the assumption that the protocol being encoded is alternating 2 .

It is not hard to see that the interactive coding scheme of Kol and Raz [12] also works for the C Γ,𝜖 channel, for every Γ. Their result, stated for such channels, is that for any 𝜖 > 0, any alphabet set Γ, and any alternating protocol Π with alphabet Γ, there exists a protocol Π ′ that simulates Π over C Γ,𝜖 with negligible error, and has length |Π| • (1/𝑟 𝜖 + 𝑜 (1)), where |Π| is the length of Π. Observe that, as in the classical setting, the maximum rate approaches 1 as 𝜖 approaches 0. Following [12], the dependence of the maximum rate on 𝜖, under the same alternating turns assumption, was further improved by [9] to 1 -O ( √ 𝜖), and was also studied for other two-way channels, including the adversarial channel [4,9], the (adversarial) feedback channel [7,14], the adversarial erasure channel [7], and the adversarial insertion-deletion channel [10].

Our Result

The main result of this paper is Theorem 1.1, showing that in the general case, where the order of speaking in the noiseless communication protocols Π may be arbitrary, the maximum achievable rate is bounded away from 1.

Theorem 1.1. For every 𝜖 > 0, there exists a set Γ and a deterministic protocol Π with alphabet Γ, such that any randomized protocol Π ′ that simulates Π over C Γ,𝜖 with probability 0.99 has length at least |Π|/(1 -Ω(1)).

Observe that since Theorem 1.1 holds for the C Γ,𝜖 channel that has stochastic noise and for public-coin protocols Π ′ , it also holds for adversarial noise and private-coin protocols. Furthermore, our proof of Theorem 1.1 actually proves a much stronger claim (see Section 2). For example, it implies that the maximum rate of an interactive code over the feedback channel that randomly erases a single communicated symbol (i.e., one of the sent symbols, selected uniformly at random, is received as '⊥' and the sender is notified) is only 1 -Ω(1) (cf. the results of [4,7,9,10,12,14] for such channels with maximum rate approaching 1).

We mention that our result settles the (non-binary version) of a conjecture by Haeupler (Conjecture 1.1 in [9]), that also appears in Haeupler and Gelles (Question 3 in Section 7 of [7]) and in Gelles's excellent survey (Question 2 in Section 5 of [6]). While lower bounds on the maximum rate of various two-way channels (i.e., upper bounds on the overhead of interactive codes) are known, prior to our work, the only non-trivial upper bound was due to [12] and is extremely involved (see Section 1.2).

We also mention that Theorem 1.1 uses a large alphabet set (specifically, we need |Γ| = poly(|Π|)), as for such alphabets the single erased symbol cannot be guessed by the receiver with high probability (in the binary |Γ| = 2 case, the erased symbol can be guessed with probability 1 2 ). Nevertheless, we believe that Theorem 1.1 still holds for the binary setting (fixing Γ = {0, 1}), and proving it is an outstanding question we leave open. Other interesting directions for future work include finding the maximum rate of interactive codes over C Γ,𝜖 , say when 𝜖 approaches 0, and characterizing the łhardž communication orders resulting in maximum rates bounded away from 1.

Finally, we wish to point out a corollary of Theorem 1.1: Many works involving interactive protocols (in the noisy or noiseless settings) assume an alternating order of speaking, as it is often simpler to deal with and only incurs at most a factor 2 blowup to the communication. Theorem 1.1 shows that this transformation of general protocols to alternating ones incurs at least a factor 𝑐 blowup, for some 𝑐 > 1: Assume that the blowup is only by a 1 + 𝑜 (1) factor. By converting the hard-to-simulate protocol Π from Theorem 1.1 to a protocol with alternating turns and then applying the [12] scheme, we obtain a noise-resilient protocol Π ′ that simulates Π with only 1 + 𝑜 (1) blowup to the communication, in contradiction to Theorem 1.1.

1.1.1 Techniques. The proof of Theorem 1.1 is quite involved and a detailed overview can be found in Section 2. In this section we give some of the highlights of our proof.

Theorem 1.1 is proved by combining Theorem 4.1 and Theorem 4.2. As mentioned above, our result holds even over the very mildly noisy channel that has feedback and only randomly erases a single communicated symbol. Theorem 4.1 considers a pointer chasing protocol with order of speaking 𝜎foot_2 and shows that it can only be simulated over this mildly noisy channel by a protocol with order of speaking 𝜎 ′ , for which 𝜎 is a strong subsequence of 𝜎 ′ . By a strong subsequence, we mean that for most coordinates 𝑖 ′ of 𝜎 ′ , 𝜎 remains a subsequence of 𝜎 ′ even after coordinate 𝑖 ′ is removed. Observe that given Theorem 4.1, to prove Theorem 1.1, all we have to do is exhibit a 𝜎 such that any 𝜎 ′ for which 𝜎 is a strong subsequence of 𝜎 ′ is a constant factor longer than 𝜎. This is done in Theorem 4.2.

At a high level, Theorem 4.1 is proved by proving a generalized pointer chasing lower bound: while prior pointer chasing lower bounds assume that players alternate (e.g., [13]), our proof holds for any order of speaking. To analyze cases where one of the parties speaks in several consecutive rounds, we use a lower bound for a generalization of the well-known Index problem, where the communication is not one-way, but the party holding the index speaks substantially less than what it takes to convey the index. To see why this lower bound is useful, assume for example that in the noiseless protocol Alice speaks three times and then Bob speaks once, i.e., 𝜎 = 𝐴𝐴𝐴𝐵. We think of Alice's message in those three rounds as an index 𝑖, and of Bob's input as a vector 𝑣. When Bob speaks in the fourth round he gives 𝑣 𝑖 to Alice. Now consider a simulation protocol with order of speaking 𝜎 ′ = 𝐵𝐴𝐵𝐴𝐵𝐴. Can Bob give 𝑣 𝑖 to Alice? We show that he cannot. The reason is that Alice only speaks in two instead of three rounds before Bob's final round, thus she can only give partial information about 𝑖, which is not enough for Bob to compute 𝑣 𝑖 . Theorem 4.2 is a purely combinatorial claim about strong subsequences, and is shown using the probabilistic method. We provide a detailed overview in Section 2.2, but for the high level idea, consider, for any 𝑇 > 0 the pair of strings (𝜎, 𝜎 ′ ) = (𝐴𝐵) 𝑇 , (𝐴𝐵) 𝑇 +1 , and observe that 𝜎 is a strong subsequence of 𝜎 ′ and 𝜎 ′ is almost the same length as 𝜎. Roughly speaking, our proof shows that the only reason 𝜎 is a subsequence of 𝜎 ′ for such a short 𝜎 ′ , is that 𝜎 is highly łpredictablež, in the sense that one can łguessž the symbols after coordinate 𝑖 based on the previous symbols. We formalize this notion and show that a uniformly random 𝜎 is not predictable, and use this to show that for most 𝜎, no short 𝜎 ′ will be such that 𝜎 is a strong subsequence of 𝜎 ′ .

Additional Related Work

We next survey the most relevant work on the maximum rates of interactive codes over different channels.

The C {0,1},𝜖 channel. The study of error correcting codes for interactive communication was pioneered by Schulman [15], who showed how to transform any interactive communication protocol over the (noiseless) binary channel to an equivalent noise-resilient protocol that works over the (two-way) C {0,1},𝜖 channel, with only a constant overhead in the communication. This shows that for any 𝜖 < 1 2 , the maximum rate of an interactive code over C {0,1},𝜖 is at least some constant strictly greater than 0.

Kol and Raz [12] studied the maximum rate 𝑟 𝜖 achievable by any interactive code over C {0,1},𝜖 , but as mentioned above, it is not hard to see that their results hold for every channel C Γ,𝜖 . They showed that for alternating noiseless protocols and protocols whose communication order is periodic with a small period, 𝑟 𝜖 = 1-𝑂 √︁ H(𝜖) . The assumption that the noiseless protocol is alternating (or has a small period) is crucial as their coding scheme uses the rewind-iferror mechanism [15], where the parties run the noiseless protocol over the noisy channel, and periodically compare their received transcripts to detect errors. If an error was detected, the parties łrewindž to the last agreed upon point and continue the execution of the noiseless protocol from that point. Since the noiseless protocol is assumed to be alternating, by taking the order of speaking of the simulating protocol to also be alternating, they can ensure that when rewinding, the order of speaking in the simulation matches the assumed order of speaking in the noiseless protocol. Kol and Raz also proved a matching upper bound of 1 -Ω √︁ H(𝜖) for some carefully chosen communication orders 4 . We mention that the Kol-Raz result gives the first separation between the maximum rate of classical error correcting codes and that of interactive codes, and observe that Theorem 1.1 gives a substantially stronger separation.

Building on [12] and also assuming an alternating order of speaking, [8] presented a deterministic coding scheme that achieves a rate of 𝑟 𝜖 (the [12] scheme is randomized), and [2] gave a coding scheme that handles larger 𝜖's (observe that the [12] scheme is only meaningful for small 𝜖's). Specifically, [2] showed that the maximum rate of interactive codes over C {0,1},𝜖 is at least 0.0302 times the maximum rate of classical error correcting codes over C {0,1},𝜖 .

Other (non-adaptive) channels. The maximum rates of interactive codes over other two-way channels, that are well studied in the context of classical codes, were also considered with the alternating communication order assumption. Pankratov [14] studied the rate of interactive codes over channels with random errors and feedback, and gave a scheme with rate 1 -𝑂 ( √ 𝜖). Haeupler and Gelles [7] improved his result and gave a scheme with rate 1 -Θ(H(𝜖)) that works for the adversarial feedback channel. A scheme with the same rate was also given by [7] for the adversarial erasure channel. The adversarial channel with corruption errors (bit flips) was considered in [3,4,9,16], and an interactive code with rate 𝑟 𝜖 for this model was presented in [4]. The adversarial binary insertion-deletion channel was considered by [10], who demonstrated an interactive coding scheme with rate 𝑟 𝜖 for it.

Adaptive channels. In this paper as well as in most of the prior works on interactive coding, including all the paper surveyed so far, the assumption is that the protocols Π and Π ′ have a nonadaptive (a.k.a, oblivious or static) communication order, meaning 4 Specifically, the upper and lower bounds match when the communication order is periodic with a period 𝑘 that satisfies 𝜖 = Θ log 𝑘 𝑘 2 . Indeed, Hauepler and Velingker [11] showed that if the parties alternate in sending 𝑘 = Ω (poly(1/𝜖 ) ) consecutive symbols, then the maximum rate is 1 -Θ(H(𝜖 ) ), violating the upper bound of [12]. that the order of communication in the protocol is fixed in advance. Haeupler [9] considered the adaptive setting, where at any round, each party decides whether to send a bit or listen for one based on its input and received transcript (which, in turn, depends on the channel's noise). Observe, however, that protocols in these models may have several parties attempting to send a symbol in the same round, or even no senders at all, and the received bits in these cases need to be specified.

Haeupler [9] constructed interactive codes that encode nonadaptive protocols Π (with any communication order) by adaptive protocols over the C {0,1},𝜖 channel with rate 1 -O √ 𝜖 , bypassing the upper bound of [12]. Put together, [12] and [9] imply a separation between the maximum rates obtained via adaptive and non-adaptive encodings. [9] conjectured that this separation can be strengthened, even for a single erasure error, and our Theorem 1.1 proves his conjecture. We mention that other adaptive models were studied in the literature, see e.g., [1,5].

OVERVIEW

Our main result (Theorem 1.1) says that regardless of how small the noise parameter 𝜖 is, the overhead required to simulate a noiseless channel over a noisy channel that corrupts each symbol with probability 𝜖 independently, is a constant strictly larger than 1. As mentioned in Section 1.1, we will actually prove a much stronger version of this, showing that it holds even if the channel corrupts exactly one (uniformly chosen) round, and the parties know in advance which round it is (and therefore, can change the simulation protocol they use arbitrarily based on this round, as long as this change does not affect the order in which the parties speak in the other rounds).

Showing a lower bound for a simulation protocol in a noise model that allows the protocol to change in response to the noise essentially means that we have to show a lower bound for a noiseless protocol, where all we know about the noiseless protocol is that its order of speaking is the same regardless of which round is corrupted by noise. Thus, a big part of our proof (Section 5) is, given two orders of speaking 𝜎, 𝜎 ′ , understanding when can noiseless protocols with order of speaking 𝜎 ′ simulate noiseless protocols with order of speaking 𝜎. This part subsumes and generalizes famous łpointerchasingž and łround-complexityž lower bounds in communication complexity [13, e.g.] and is overviewed in Section 2.1. The answer turns out to be quite elegant: 𝜎 ′ can simulate 𝜎 if and only if 𝜎 is a subsequence of 𝜎 ′ .

We now look back at our original problem of designing a noiseless protocol Π that cannot be simulated by any (short) protocol over a noisy channel, even when the noise corrupts only one random symbol in the simulation protocol that is known to the parties as soon as they fix the order of speaking in the simulation protocol. Having shown that an order 𝜎 ′ can simulate 𝜎 if and only if 𝜎 is a subsequence of 𝜎 ′ , this means that we have to construct an order of speaking 𝜎 (which will be the order in which the parties speak in Π) such that any short order of speaking 𝜎 ′ satisfies the property that 𝜎 is not a łstrongž subsequence of 𝜎 ′ . By that we mean that removing one uniformly chosen coordinate from 𝜎 ′ ensures that, with high probability, 𝜎 is not a subsequence of 𝜎 ′ with that coordinate removed (see Definition 3.7). This is the second main part of our proof and is described in Section 6 and overviewed in Section 2.2.

Lower Bounds on Noiseless Simulations

Recall that the order of speaking for a protocol Π of length 𝑇 is a string 𝜎 ∈ {𝐴, 𝐵} 𝑇 that captures the order in which Alice and Bob speak in Π, in the sense that, for all 𝑖 ∈ [𝑇 ], party 𝜎 𝑖 is the party speaking in round 𝑖 of Π. The goal of this section is to show that, given any two orders of speaking 𝜎 and 𝜎 ′ , all (noiseless) protocols with order of speaking 𝜎 can be simulated by (noiseless) protocols with order of speaking 𝜎 ′ if and only if 𝜎 is a subsequence of 𝜎 ′ . The łifž direction is straightforward and we shall focus on showing the łonly ifž direction.

We argue this in the contrapositive. Suppose that two orders 𝜎 and 𝜎 ′ are given such that 𝜎 is not a subsequence of 𝜎 ′ . We first note that if 𝜎 is alternating, i.e., 𝜎 is of the form 𝐴𝐵𝐴𝐵𝐴 . . . , then the desired result follows from (an easy extension of) the pointer chasing lower bounds in [13] and subsequent work. However, a lower bound only for alternating 𝜎 is not good enough for us, as we want the lower bound for a string 𝜎 such that any short 𝜎 ′ satisfies the property that 𝜎 is not a strong subsequence of 𝜎 ′ . This is provably not the case for alternating 𝜎 as for any alternating 𝜎, the string 𝜎 ′ = 𝐴𝐵||𝜎 satisfies the property that 𝜎 is a strong subsequence of 𝜎 ′ , where || denotes concatenation.

However, as our lower bound must subsume these lower bounds, it is important to understand them. For this, consider the case when 𝜎 = 𝐴𝐵 so that 𝜎 ′ (as 𝜎 cannot be a subsequence of 𝜎 ′ ) is of the form 𝐵𝐵 . . . 𝐴𝐴𝐴𝐴 . . . , say 𝜎 ′ = 𝐵𝐵𝐵𝐴𝐴𝐴. Consider now the well-known Index problem, where Bob has a large array and Alice has an index for the array, and the goal of the parties is to output the element at Alice's index in Bob's array. There is a simple protocol with order of speaking 𝜎 that solves this problem, where Alice first sends her index and then Bob sends the element at that index. However, if the order of speaking is restricted to be 𝜎 ′ there is no way for Bob to send the right element to Alice, as all his messages are before he acquires any knowledge of Alice's index (unless of course, he sends to Alice the entire array, but this is impossible if Alice's alphabet is large enough).

For our more general result, we first extend the above lower bound to a more general class of 𝜎 that has many Alice messages before the last Bob message, say, 𝜎 = 𝐴𝐴𝐴𝐵. The hard protocol for these 𝜎 is also the protocol for the Index problem except that this time, Alice's index is so large that it will not fit in one message (and requires three messages). For all 𝜎 ′ where all Bob's messages precede all Alice's messages, the argument is the same as before, but this time there are additional 𝜎 ′ that are not of the form above and satisfy that 𝜎 is not a subsequence of 𝜎 ′ , for example 𝜎 ′ = 𝐵𝐴𝐵𝐴𝐵𝐴.

When 𝜎 ′ = 𝐵𝐴𝐵𝐴𝐵𝐴, as a protocol with order of speaking 𝜎 ′ proceeds, Bob does get some messages from Alice (in rounds 2 and 4) but these messages are not long enough to contain her entire index. Thus, to show a lower bound for such 𝜎 ′ , we need to extend the aforementioned lower bound for Index to work for protocols where Bob has partial information about Alice's index. This is exactly what we do, showing that such partial information from Alice cannot help Bob in guessing the right index a whole lot, and he still cannot send her the right index without sending a huge portion of his array. However, Bob cannot send a huge portion without having high communication, which is impossible if 𝜎 ′ is not much longer than 𝜎.

To extend this argument to general 𝜎 and 𝜎 ′ such that 𝜎 is not a subsequence of 𝜎 ′ , we break the string 𝜎 into łintervalsž, where an interval is defined a set of consecutive rounds where the same party is speaking, e.g., the first three Alice rounds in 𝜎 = 𝐴𝐴𝐴𝐵. For each such interval starting from the first, we treat it like the Index problem above, and show that the interval cannot be simulated unless the party speaking in that interval has spoken enough times in the simulation. Once the party has spoken enough times, we remove the interval from 𝜎 and the corresponding rounds from 𝜎 ′ and arrive at a smaller problem with a fewer number of intervals. As 𝜎 is not a subsequence of 𝜎 ′ , we will run out of rounds in 𝜎 ′ before we run out of intervals in 𝜎, giving us a trivial protocol for a non-trivial task, a contradiction.

Analysis of Strong Subsequences

In this part, our goal is to show that there exists an order of speaking 𝜎 ∈ {𝐴, 𝐵} * , such that for any 𝜎 ′ ∈ {𝐴, 𝐵} * for which 𝜎 is a strong subsequence of 𝜎 ′ , it holds that 𝜎 ′ is a constant factor longer than 𝜎. Recall that 𝜎 is a strong subsequence of 𝜎 ′ if, for most coordinates 𝑖 of 𝜎 ′ , it holds that 𝜎 is a subsequence of 𝜎 ′ with coordinate 𝑖 removed. Throughout this section, we will disregard the connection of 𝜎 and 𝜎 ′ to communication protocols, and look at them simply as strings in {𝐴, 𝐵} * . Also, we let 𝑇 be the length of 𝜎 and assume that the length of 𝜎 ′ is 𝑇 ′ = (1 + 𝛿)𝑇 , where 𝛿 > 0 is a small constant.

Patterns. We will show this using the probabilistic method, categorizing the relevant pairs (𝜎, 𝜎 ′ ) into various łpatternsž, where for each pattern 𝜌 and each 𝜎, there is exactly one 𝜎 ′ such that the pair (𝜎, 𝜎 ′ ) is in the pattern 𝜌. We then show that, for every fixed pattern, and a randomly chosen pair (𝜎, 𝜎 ′ ) in the pattern, the probability that 𝜎 is a strong subsequence of 𝜎 ′ is extremely small, small enough to union bound over all the patterns, and our result follows.

Specifically, a pattern for us will be defined by a string 𝜌 ∈ {𝐴, 𝐵, •} 𝑇 ′ such that the number of coordinates of 𝜌 that are equal to the łbulletž symbol • is 𝑇 . We say that a pair (𝜎, 𝜎 ′ ) is in the pattern 𝜌 if it holds that upon łinsertingž the string 𝜎 in the bullet coordinates of 𝜌, we get the string 𝜎 ′ . Note that we can indeed restrict attention to the pairs (𝜎, 𝜎 ′ ) that are in some pattern, as if a pair is not in any pattern, then it must be the case that 𝜎 is not a subsequence of 𝜎 ′ , and therefore, it cannot be a strong subsequence of 𝜎 ′ either. Moreover, the number of patterns 𝜌 is at most

•𝑇 and we will ensure that, assuming 𝛿 is a small enough constant, the relevant probabilities are small enough for a union bound over all the patterns.

Analyzing a toy pattern. Following the above framework, we now fix a pattern 𝜌 and show that for a random pair (𝜎, 𝜎 ′ ) in 𝜌, we have that 𝜎 is not a strong subsequence of 𝜎 ′ with high probability. The high level idea here is best understood by taking 𝜌 = • 𝑇 , the 𝑇 -length string each of whose coordinates are •, even though this is not a valid pattern according to the definition above. However, picking 𝜌 = • 𝑇 also means that the only way a pair (𝜎, 𝜎 ′ ) can be in this pattern is if 𝜎 = 𝜎 ′ , implying that 𝜎 is trivially not a strong subsequence of 𝜎 ′ = 𝜎. Thus, to make the argument non-trivial, we will show that, for a uniformly random 𝜎 ∈ {𝐴, 𝐵} 𝑇 , even a prefix of 𝜎 of length 0.9𝑇 is not a strong subsequence of 𝜎.

For this, consider what happens if we erase the first coordinate of 𝜎 to get a string 𝜎 -1 , and try to estimate the length of the longest prefix of 𝜎 that is a subsequence of 𝜎 -1 (the case when a different coordinate is erased is similar). To estimate the length of the longest prefix, we consider the greedy algorithm łmatchingž the string 𝜎 to the string 𝜎 -1 : Namely, match each coordinate of 𝜎 to the earliest coordinate possible 5 in 𝜎 -1 . To analyze this algorithm, for all 𝑖 ∈ [𝑇 ], define lag 𝑖 to be the difference between 𝑖 and the coordinate in 𝜎 corresponding to the coordinate in 𝜎 -1 that 𝑖 is matched to. For example, if coordinate 1 of 𝜎 is matched to the first coordinate in 𝜎 -1 (equivalently, the second coordinate in 𝜎), then,

As 𝜎 is uniformly random in {𝐴, 𝐵} 𝑇 , each coordinate of 𝜎 is uniformly and independently random in {𝐴, 𝐵}, and thus each coordinate in 𝜎 will take (in expectation) two coordinates of 𝜎 -1 to find a match. This means that, in expectation 6 , we have lag 𝑖 ≥ lag 𝑖 -1 +1. Using concentration bounds, we can conclude that, except with probability exponentially small in 𝑇 , at most a 0.9 fraction of the coordinates will end up being matched, implying that the length of the longest prefix of 𝜎 that is a subsequence of the resulting string 𝜎 -1 is at most 0.9𝑇 , as desired.

Towards actual patterns. The argument above does not extend to actual patterns 𝜌 ∈ {𝐴, 𝐵, •} 𝑇 ′ , but for a very specific reason: To understand the reason, note that the argument above crucially relied on the fact that lag is non-zero throughout (in fact, it starts from 1 and never decreases). This means that we are always trying to compare a coordinate in 𝜎 to another łfreshž coordinate, which is independently and uniformly random, and this allowed us to say that lag increases by 1 in expectation. In fact, if the lag were to have been 0, then we would be comparing every coordinate in 𝜎 to itself, which means that it will aways match, and we will therefore be able to match all of 𝜎. Now, observe that the presence of non-bullet coordinates in 𝜌 can actually decrease the lag and make it 0, ruining our argument above. For an example, consider the case 𝑇 ′ = 𝑇 + 2, and the pattern 𝜌 = •, 𝐴, 𝐵, • 𝑇 -1 . Specifically, consider the case where the first coordinate is erased, creating a lag of 1. However, as the two coordinates 𝐴, 𝐵 immediately follow the erased coordinate, one can always match the first coordinate of 𝜎 to one of these coordinates, bringing the lag back down to 0, and allowing the rest of 𝜎 to be matched as is.

To get around this, we use the observation that any non-bullet symbol in 𝜌 can decrease the lag by at most 1. Thus, as the number of non-bullet symbols in 𝜎 is 𝛿𝑇 , if we could somehow magically start with lag = 𝛿𝑇 , then, lag will never vanish for any fixed pattern 𝜌 and we can apply exactly the same analysis as in the toy pattern above to get that 𝜎 will not be a subsequence except with probability exponentially small in 𝑇 . This probability is small enough for us to union bound over all possible 𝜌 and get that except with probability exponentially small in 𝑇 , a uniformly random 𝜎 will not have any 𝜎 ′ such that 𝜎 is a strong subsequence of 𝜎 ′ .

Starting with a small lag. All we need to do now is to apply the argument above for large initial lag to the case at hand where the initial lag is 1. For this, observe from our example above (and also in the toy example 𝜌 = • 𝑇 ) that lag will actually increase as 𝑖 increases, in the sense that the final lag is at least Ω(𝑇 ) more than the initial lag, except with exponentially small probability in 𝑇 . This holds despite the fact that we have a small number (= 𝛿𝑇 ) of non-bullet symbols, as each such symbol can decrease lag by at most 1, but the much larger number (= 𝑇 ) of bullet symbols, each increasing lag by 1 in expectation (as the small number of non-bullet symbols are not enough to make lag vanish), will eventually override the effect of the non-bullet symbols.

The fact that the lag increases can be used as follows: Suppose we are currently considering an 𝑖 such that lag 𝑖 is some value 𝐿 > 0. Consider the pattern starting from the coordinate where 𝑖 is matched and look at the segment consisting of the next, say, 𝐿/ √ 𝛿 coordinates. As only a 𝛿 fraction of the coordinates are nonbullet, this segment is expected to have √ 𝛿 • 𝐿 < 𝐿 of non-bullet symbols. As the number of non-bullet symbols is smaller than the initial lag, we can conclude that (even after union bounding over all possible ways to place the non-bullet coordinates) except for a łbadž event that happens with probability exponentially small in 𝐿, this segment is expected to increase the lag to 𝐿 ′ = Ω(𝐿/ √ 𝛿). Now, we can consider the next segment of length 𝐿 ′ / √ 𝛿, and show that except with probability exponentially small in 𝐿 ′ , this segment is expected to increase lag even more. The increasing length of these segments allows us to show that the sum of the bad probabilities converges to a constant, implying that for any erased coordinate 𝑖, one of the following holds: (1) The fraction of non-bullet symbols in one of the segments that are generated is much larger than 𝛿. (2) There exists a segment generated from 𝑖 for which the bad event occurs. (3) When 𝑖 is erased, the final lag increases to be Ω(𝑇 ).

By Markov's inequality, both Items 1 and 2 will happen for at most a small constant fraction of 𝑖. Thus, there exists a 𝜎 such that for most 𝑖, Item 3 will occur, implying that, for any 𝜎 ′ such that 𝜎 is a subsequence of 𝜎 ′ , we have that 𝜎 is not a subsequence of 𝜎 ′ -𝑖 . It follows that there exists a 𝜎 such that for no 𝜎 ′ is it the case that 𝜎 is a strong subsequence of 𝜎 ′ , as desired. In terms of organization, the definition of 𝑖 in Item 2 is formalized in Definition 6.6 and the proof that there is a small number of such 𝑖 is in Lemmas 6.7 and 6.8. Analogous statements about Item 1 can be found in Lemma 6.10 while the proof of Item 3 can be found in Section 6.6 (specifically, Lemma 6.12).

MODEL AND PRELIMINARIES 3.1 Notation

For 𝑛 > 0, we use [𝑛] to denote the set {1, 2, . . . , 𝑛}. For 𝑎, 𝑏 > 0, we use [𝑎, 𝑏] to denote the set {𝑎, 𝑎 + 1, . . . , 𝑏}. Additionally, we use (𝑎, 𝑏] to denote the set {𝑎 + 1, . . . , 𝑏}. The notations [𝑎, 𝑏) and (𝑎, 𝑏) are defined analogously.

Let Σ be an alphabet set and 𝑛 > 0 be an integer. For a string 𝑠 ∈ Σ 𝑛 and a set 𝐼 ⊂ [𝑛], we use 𝑠 𝐼 to denote the |𝐼 |-length string obtained by taking only those coordinates of 𝑠 that are in 𝐼 , e.g., we have (𝐴𝐵𝐴𝐴𝐵) {1,3,4} = 𝐴𝐴𝐴. For 𝑖 ∈ [𝑛], we sometimes abbreviate 𝑠 {𝑖 } to 𝑠 𝑖 , 𝑠 [𝑖 ] to 𝑠 ≤𝑖 , and 𝑠 [𝑛]\{𝑖 } to 𝑠 -𝑖 . We also use the notations 𝑠 <𝑖 , 𝑠 >𝑖 and 𝑠 ≥𝑖 that are defined analogously. Whenever we have 𝐶 ∈ {𝐴, 𝐵}, we use 𝐶 to denote the unique element of {𝐴, 𝐵} not equal to 𝐶.

Throughout this paper, we use sans-serif letters to denote random variables.

Embedding Strings

Let 𝜎, 𝜎 ′ ∈ {𝐴, 𝐵} * and 𝑇 = |𝜎 | and 𝑇 ′ = |𝜎 ′ |. For 𝑖 ∈ {0} ∪ [𝑇 ], we define the function Emb(𝜎, 𝜎 ′ , 𝑖) inductively by Emb(𝜎, 𝜎 ′ , 0) = 0 and as follows when 𝑖 > 0:

Note that the min above is taken over a finite non-empty set, and is therefore well-defined. We also define the set:

(

We say that 𝜎 is a subsequence of

we have:

We also use the following lemmas throughout our paper. The formal proofs of Lemmas 3.2 to 3.6 are omitted for space and can be found in the full version of the paper.

Moreover, we also have:

Our Noisy Channel

Let Γ be a set with |Γ| ≥ 2. A (deterministic) protocol with the alphabet set Γ is defined by a tuple:

where: (1) 𝑇 > 0 is a parameter denoting the length of the protocol, (2) 𝜎 ∈ {𝐴, 𝐵} 𝑇 is a string that determines which party speaks when (i.e., for all 𝑖 ∈ [𝑇 ], party 𝜎 𝑖 is the unique party speaking in round 𝑗), (3) X 𝐶 for 𝐶 ∈ {𝐴, 𝐵} is the input set of party 𝐶, (4) Y is the set of possible outputs of the protocol, ( 5) For all 𝑖 ∈ [𝑇 ], 𝑀 𝑖 : X 𝜎 𝑖 × Γ 𝑖 -1 → Γ is a function that computes the message sent in round 𝑖 based on the input of the party 𝜎 𝑖 speaking in round 𝑖 and the transcript ∈ Γ 𝑖 -1 received by party 𝜎 𝑖 in the first 𝑖 -1 rounds, (6) out 𝐶 : Γ 𝑇 → Y for 𝐶 ∈ {𝐴, 𝐵} are functions that each player uses to compute the output from the transcript of the protocol. We suppress items on the right hand side of Eq. ( 3) when they are clear from context. We use the notation spkrs(Π) = 𝜎 and |Π| = 𝑇 . We define a randomized protocol Π to be a distribution over deterministic protocols Π that all have the same value of 𝑇 , 𝜎, X 𝐴 , X 𝐵 , Y . We define spkrs(Π) and |Π| to be the common value of spkrs(Π) and |Π| respectively.

Execution of a protocol. Let Π be a protocol as above and 𝜖 ≥ 0. We now describe how Π is executed over the channel C Γ,𝜖 that corrupts each sent symbol (independently) to a uniformly random symbol in Γ with probability 𝜖. To describe this execution, we let ★ be a special symbol not in Γ indicating łno noisež and 𝑁 ∈ (Γ ∪ {★}) 𝑇 be a noise vector such that for all 𝑖 ∈ [𝑇 ], the symbol 𝑁 𝑖 = ★ with probability 1 -𝜖 and a uniformly random symbol from Γ with probability 𝜖 (independently for all 𝑖), so that 𝑁 captures the noise inserted by the aforementioned channel. We shall abuse notation and use C Γ,𝜖 to denote both the channel and the above distribution over noise vectors.

The execution begins with both parties 𝐶 ∈ {𝐴, 𝐵} having input 𝑥 𝐶 ∈ X 𝐶 and proceeds in 𝑇 rounds, maintaining the invariant that before round 𝑖 ∈ [𝑇 ], both parties 𝐶 ∈ {𝐴, 𝐵} have a partial transcript Π 𝐶 <𝑖 ∈ Γ 𝑖 -1 . In round 𝑖, party 𝜎 𝑖 computes the symbol 𝛾 𝑖 = 𝑀 𝑖 𝑥 𝜎 𝑖 , Π 𝜎 𝑖 <𝑖 , appends it to its own partial transcript, and sends it over the channel to the other party 𝜎 𝑖 .

The noise 𝑁 then acts on the symbol as follows: If 𝑁 𝑖 = ★, then the symbol is sent uncorrupted and party 𝜎 𝑖 receives the symbol 𝛾 𝑖 . Otherwise, we have 𝑁 𝑖 ∈ Γ and party 𝜎 𝑖 receives the symbol 𝑁 𝑖 . In either case, party 𝜎 𝑖 appends the received symbol to its partial transcript and the execution proceeds to the next round.

After the 𝑇 rounds are over, each party 𝐶 ∈ {𝐴, 𝐵} outputs out 𝐶 Π 𝐶 ≤𝑇 ∈ Y. Note that this execution is entirely determined by the triple 𝑥 𝐴 , 𝑥 𝐵 , 𝑁 , which we shall often write as (𝑋, 𝑁 ) using 𝑋 to denote the pair of inputs 𝑥 𝐴 , 𝑥 𝐵 . This fact allows us to write Π 𝐶 𝑖 (𝑋, 𝑁 ), Π 𝐶 ≤𝑖 (𝑋, 𝑁 ), etc. to denote the corresponding value in the execution of Π in the presence of noise 𝑁 when the inputs are 𝑋 . For 𝐶 ∈ {𝐴, 𝐵}, we also define the notation res 𝐶 Π (𝑋, 𝑁 ) to denote the output of party 𝐶 in the above execution and res Π (𝑋, 𝑁 ) = res 𝐴 Π (𝑋, 𝑁 ), res 𝐵 Π (𝑋, 𝑁 ) . We omit 𝑁 from the above notations when 𝜖 = 0 and the execution is noiseless, as in this case, 𝑁 is always the vector with all coordinates equal to ★. Note that, in this case, the transcripts for Alice and Bob are the same and we can omit the superscript 𝐶 in the notation.

Simulations and hole simulations. Let Γ be an alphabet set as above. Let Π and Π ′ be two randomized protocols with alphabet Γ and with the same input sets X 𝐴 , X 𝐵 for Alice and Bob. For 𝑝 ∈ [0, 1] and 𝜖 ≥ 0, we say the protocol Π ′ simulates the protocol Π over the channel C Γ,𝜖 with probability 𝑝 if for all 𝑥 𝐴 ∈ X 𝐴 , 𝑥 𝐵 ∈ X 𝐵 , it holds that

Throughout this text, the protocol Π being simulated will be deterministic and we shall omit it from the subscript above. As our main result in a lower bound, the fact that Π is deterministic only makes our result stronger. As Γ is determined by Π, we shall sometimes omit writing łover the channel C Γ,𝜖 ž when 𝜖 = 0.

For our proof of Theorem 1.1, we actually work with a different (and weaker 7 ) notion of simulation that we call łhole simulationž and is defined as follows: Let 𝜎 ′ ∈ {𝐴, 𝐵} * and Π be a protocol as above. For 𝑝 ∈ [0, 1], we say that 𝜎 ′ hole-simulates Π with probability 𝑝 if there exists a set

10 such that for all 𝑖 ′ ∈ 𝐼 ′ , there exists a randomized protocol Π ′ 𝑖 ′ with alphabet Γ and the same input sets as Π that simulates the protocol Π (over the channel C Γ,0 ) with probability 𝑝 and satisfies spkrs Π ′ 𝑖 ′ = 𝜎 ′ -𝑖 ′ .

Pointer Chasing

Let 𝑚,𝑇 ∈ N. We inductively define the function PC

PROOF OF THEOREM 1.1

The goal is section is to prove Theorem 1.1 assuming two other theorems that we shall prove in the following sections. We start by stating these two theorems. Theorem 4.2. For all 𝑇 > 0, there exists 𝜎 ∈ {𝐴, 𝐵} 𝑇 such that for all 𝜎 ′ ∈ {𝐴, 𝐵} * such that 𝜎 is a strong subsequence of 𝜎 ′ , we have

We are now ready to prove Theorem 1.1 (assuming Theorems 4.1 and 4.2).

Proof of Theorem 1.1. Fix 𝜖 > 0 and assume that 𝜖 < 0.001 without loss of generality. Define 𝑇 = 1 𝜖 2 and let 𝜎 be as promised by Theorem 4.2. Define Γ = (200𝑇 ) 200 and Π = PC 𝜎 . Let Π ′ be a randomized protocol that simulates Π with over the channel C Γ,𝜖 with probability 0.99 and 𝜎 ′ = spkrs(Π). As the proof is trivial otherwise, assume that |𝜎 ′ | = |Π ′ | ≤ 5𝑇 . We claim that 𝜎 ′ hole simulates PC 𝜎 with probability 0.5. This finishes the proof as it implies using Theorem 4.1 that 𝜎 is a strong subsequence of 𝜎 ′ which using Theorem 4.2 means that |𝜎 ′ | ≥ 1 + 10 -100 • 𝑇 , as desired.

It remains to show the claim. To this end, let 𝑇 ′ = |𝜎 ′ | and for 𝑖 ′ ∈ [𝑇 ′ ], define the protocol Π ′ 𝑖 ′ with spkrs(Π ′ 𝑖 ′ ) = 𝜎 ′ -𝑖 ′ as follows: For 𝑡 ∈ {0} ∪ [𝑇 ′ ], let 𝑝 𝑡 = 𝑇 ′ 𝑡 • 𝜖 𝑡 (1 -𝜖) 𝑇 ′ -𝑡 be the probability that the channel C Γ,𝜖 corrupts exactly 𝑡 symbols in Π ′ . This means that 𝑝 𝑡 1-𝑝 0 is the probability the channel C Γ,𝜖 corrupts exactly 𝑡 symbols in Π ′ conditioned on it corrupting at least one symbol. Then, the protocol Π ′ 𝑖 ′ is exactly the same as Π ′ except that it (1) It does not have round 𝑖 ′ and the party supposed to receive in this round assumes it got a uniformly random symbol in Γ. Observe that this can equivalently be seen as the channel always corrupting round 𝑖 ′ in Π ′ . (2) Samples 𝑡 ′ ∈ [𝑇 ′ ] with probability 𝑝 𝑡 ′ 1-𝑝 0 , and then artificially corrupts 𝑡 ′ -1 rounds, ignoring the bit actually received in these rounds and using a uniformly random symbol in Γ instead.

Observe that picking 𝑖 ′ ∈ [𝑇 ′ ] uniformly at random and running Π ′ 𝑖 ′ over the noiseless channel C Γ,0 is the same as running Π ′ over C Γ,𝜖 and conditioning on the fact that the channel corrupts at least one symbol. As Π ′ simulates Π with over the channel C Γ,𝜖 with probability 0.99, we get:

It follows that Pr

10 values of 𝑖 ′ , as desired. □

PROOF OF THEOREM 4.1

The goal of this section is to show Theorem 4.1. Owing to the definition of hole simulations and Definition 3.7, it suffices to show the following lemma: We prove Lemma 5.1 in the rest of this section. Fix 𝜏, Π and define 𝑛 = |𝜏 |, 𝑇 = |Π|, and 𝜎 = spkrs(Π). We shall show the lemma in the contrapositive, assuming that 𝜏 is a not subsequence of 𝜎 and showing that Π does not simulate PC 𝜏 with probability 1 𝑛 . As 𝜏, 𝜎 are fixed we shall often omit them from our notation and write Emb(•) instead of Emb(𝜏, 𝜎, •) and E instead of E(𝜏, 𝜎).

Let X 𝐴 and X 𝐵 be input sets of Alice and Bob respectively in PC 𝜏 (and therefore also in Π). Recall from Section 3.3 that we have to show that there exist 𝑥 𝐴 ∈ X 𝐴 , 𝑥 𝐵 ∈ X 𝐵 such that:

Let F be the uniform distribution over all inputs of PC 𝜏 , defined as in Section 3.4. To show the foregoing equation, we fix an arbitrary deterministic protocol Π in the support of Π and show that (noting that res PC 𝜏 (𝐹 ) = PC(𝐹 )):

Notation

For a finite non-empty set 𝑆, we shall use U (𝑆) to denote the uniform distribution over 𝑆. We omit 𝑆 from the notation when it is clear from the context. All probabilities and random variables will be defined over the randomness in F , and we will often abbreviate Pr 𝐹 ∼F to Pr for brevity of notation. Throughout, if X is a random variable and 𝑥 is a value that X can take, we sometimes abbreviate the event X = 𝑥 as simply 𝑥 when it is clear from context. Thus, we may write Pr(𝑥) instead of Pr(X = 𝑥) and Pr(• | 𝑥) instead of Pr(• | X = 𝑥). We use dist(X) to denote the distribution of a random variable X.

We will use F to denote the random variable corresponding to a sample from F and 𝐹 to denote a given value of F. Observe that 𝐹 is an 𝑛-tuple

We may combine these notations and use 𝑓 𝐴 ≤𝑖 = 𝑓 {𝑖 ′ ∈ [𝑖 ] |𝜏 𝑖 ′ =𝐴} , etc.. We will use f ≤𝑖 to denote the random variable corresponding to 𝑓 ≤𝑖 . The notations f 𝑆 , f <𝑖 , f 𝐴 , etc. are defined similarly.

Recall the functions Π 𝑡 (•) and Π ≤𝑡 (•) from Section 3.3. In this section, we extend this notation to sets 𝑆 ⊆ [𝑇 ] by defining Π 𝑆 (•) = (Π 𝑡 (•)) 𝑡 ∈𝑆 . For 𝑡 ∈ [𝑇 ], we will use Π 𝑡 = Π 𝑡 (F) to denote the random variable obtained by sampling F and outputting Π 𝑡 (F), and use Π 𝑡 to denote a value Π 𝑡 can take. The notations Π ≤𝑡 , Π 𝑆 are defined analogously.

Definitions

Recall that we fixed 𝜏 ∈ {𝐴, 𝐵} 𝑛 as the order in which the parties speak in the protocol PC 𝜏 being simulated. We also fixed a deterministic protocol Π and defined 𝑇 = |Π| and 𝜎 = spkrs(Π) ∈ {𝐴, 𝐵} 𝑇 . The set L. We consider the set of indices 𝑖 ∈ [𝑛] where the value of 𝜏 𝑖 is different from 𝜏 𝑖+1 . Define the set:

Informally, L is the rounds where 𝜏 łswitchesž from 𝐴 to 𝐵 or 𝐵 to 𝐴. Equivalently, we partition 𝜏 into consecutive intervals consisting of the same player and L is the set of endpoints of these intervals.

The element 𝑛 is added to L for convenience. For 𝑖 ∈ [𝑛], we define ℓ ≥ 𝑖 to be smallest value ℓ ∈ L satisfying ℓ ≥ 𝑖. This is well defined as 𝑛 ∈ L is one such value. Similarly, define ℓ < 𝑖 to be largest value ℓ ∈ {0} ∪ L satisfying ℓ < 𝑖. Observe that for all 𝑖 ∈ [𝑛], we have

Defining Good and Rem. For 𝑡 ∈ {0} ∪ [𝑇 ], define the set

Informally, Good gets a round 𝑡 of the protocol Π and outputs the first interval of 𝜏 that we do not expect to have fully simulated after round 𝑡. Observe that Good(𝑡)

and 𝑖 ∈ Good(𝑡). Define:

Roughly speaking, Rem 𝑖 (𝑡) is the amount of (min-)entropy remaining in the random variable PC >ℓ < 𝑖 (f ≤𝑖 ) before round 𝑡 of the protocol.

łRevealingž information. To make our analysis cleaner, we reveal some information to the players at various points in the protocol. More precisely, let 𝑡 ′ ∈ [3𝑇 ] be given and 𝐹 in the support 8 of F be arbitrary. Let 𝑡 ∈ [𝑇 ] be the unique value satisfying 3(𝑡 -1) < 𝑡 ′ ≤ 3𝑡. We shall define values Φ 𝑡 ′ (𝐹 ) inductively. If 𝑡 ′ = 3𝑡 -2, define:

If 𝑡 ′ = 3𝑡 -1, define:

Informally, this definition amounts to revealing the correct transcript for any interval at the end of the interval. Finally, if 𝑡 ′ = 3𝑡, define:

Informally, this definition amounts to revealing, at the end of an interval, whether the right answer for the next interval can be guessed with probability much better than what Rem would indicate. We will later show that, this answer is no (= 0) with high probability. Henceforth, we treat Φ the same way as Π in our notation, i.e., we let Φ 𝑡 ′ = Φ 𝑡 ′ (F) denote the random variable obtained by sampling F and outputting Φ 𝑡 ′ (F), use Φ 𝑡 ′ to denote a value Φ 𝑡 ′ can take, and define Φ ≤𝑡 ′ , Φ 𝑆 etc. analogously to Π ≤𝑡 , Π 𝑆 , etc. We claim that Φ provides all the necessary information in order to reconstruct PC(f), as claimed below.

Claim 5.2. For any ℓ ∈ L satisfying Emb(ℓ) ≤ 𝑇 , the value of Φ ≤3Emb(ℓ ) -1 fixes the value of PC(f ≤ℓ ).

The formal proof of Claim 5.2 is omitted for space and can be found in the full version of the paper.

We also claim that Φ is a transcript of a protocol. By this, we mean that each coordinate of Φ can be computed fully by just one player using only their input and the transcript Φ so far. Formally: Lemma 5.3. For 𝑡 ′ ∈ [3𝑇 ], there exists 𝜎 ′ 𝑡 ′ ∈ {𝐴, 𝐵} and a function 𝑀 ′ 𝑡 ′ such that for any 𝐹 ,

Furthermore, for 𝑡 ∈ [𝑇 ], we have that:

The formal proof of Lemma 5.3 is omitted for space and can be found in the full version of the paper.

The sets Guess and Info. We are now ready to define the sets Guess and Info, the primary focus of our analysis. For 𝑡 ∈ {0} ∪ [𝑇 ] and 𝑖 ∈ Good(𝑡), we define:

Informally, this is the set of transcripts that allow us to guess the edges in the current interval (until 𝑖) with probability better than that indicated by Rem. For 𝑡 ∈ {0} ∪ [𝑇 ] and 𝐶 ∈ {𝐴, 𝐵}, define:

Informally, this is the set of transcripts that give a lot of information about party 𝐶's input.

Properties of Info

This section is dedicated to proving Lemma 5.4, which will be key to proving our main result. Roughly, Lemma 5.4 says that transcripts are unlikely to be informative enough to be in the set Info as that requires information ≥ 𝑚 0.01 which is much more than the communication (as 𝑚 is larger than the communication to the power of 200).

Lemma 5.4. For all 𝑡 ∈ {0} ∪ [𝑇 ] and 𝐶 ∈ {𝐴, 𝐵},

For all 𝑡 ′ ∈ [3𝑇 ], let 𝜎 ′ 𝑡 ′ and 𝑀 ′ 𝑡 ′ be as in Lemma 5.3. We define for all 𝐶 ∈ {𝐴, 𝐵}, for all 𝑡 ′ ∈ {0} ∪ [3𝑇 ], for all Φ ≤𝑡 ′ , the set:

we have

Roughly, our definition of Φ ensures that the pairs of inputs that lead to the transcript Φ ≤𝑡 ′ form a combinatorial rectangle (Rec denotes rectangle), and Rec 𝐶 denotes the projection of this rectangle on party 𝐶's inputs. In other words, Rec 𝐶 is the set of all inputs of party 𝐶 that may lead to the transcript Φ ≤𝑡 ′ .

Observation 5.5. For all 𝑡 ′ ∈ [3𝑇 ], for all Φ ≤𝑡 ′ , for all 𝐶 ∈ {𝐴, 𝐵}, if 𝜎 ′ 𝑡 ′ ≠ 𝐶, Rec 𝐶 (Φ ≤𝑡 ′ ) = Rec 𝐶 (Φ <𝑡 ′ ). We now show several properties of Rec 𝐶 . The formal proofs of Lemmas 5.6 to 5.8 are omitted for space and can be found in the full version of the paper.

Lemma 5.6. For all 𝑡 ′ ∈ {0} ∪ [3𝑇 ], for all Φ ≤𝑡 ′ , the event ∀𝐶 ∈ {𝐴, 𝐵} : f 𝐶 ∈ Rec 𝐶 (Φ ≤𝑡 ′ ) and the event Φ ≤𝑡 ′ are equivalent.

Lemma 5.7. For all 𝑡 ′ ∈ {0} ∪ [3𝑇 ], for all Φ ≤𝑡 ′ ,

We now have the tools necessary to finish the proof of Lemma 5.4.

Proof of Lemma 5.4. For all Φ ≤3𝑡 ∈ Info 𝐶 (𝑡) we have:

(Eq. ( 12))

The result follows from Lemma 5.8. □

Key Lemma

We now show our key lemma.

Lemma 5.9. Let 𝑡 ∈ {0} ∪ [𝑇 ] and 𝑖 ∈ Good(𝑡). We have:

Proof. Proof by induction on 𝑡. The base 𝑡 = 0 is straightforward as we get Emb ℓ < 𝑖 = 0 which means that ℓ < 𝑖 = 0 implying that Guess 𝑖 (𝑡) = ∅. We show the result for 𝑡 > 0 assuming it holds for smaller values of 𝑡. We consider the following cases: When Emb ℓ < 𝑖 < 𝑡: At a high level, this case amounts to analyzing a variant of the well-known Index problem, where the party holding the index can communicate a small number of bits but not enough to send the entire index. Let 𝑢 = Emb ℓ < 𝑖 for convenience. Note that 𝑖 ∈ Good(𝑢). Applying the induction hypothesis on 𝑢, we get:

We assume 𝜏 𝑖 = 𝐴 as the argument for 𝜏 𝑖 = 𝐵 is analogous. For this, we shall fix an arbitrary Φ ≤3𝑢 ∉ Guess 𝑖 (𝑢), and an arbitrary 𝑓 𝐵 and show that

By Eq. ( 11), it suffices to show that:

We now focus on showing Eq. ( 14). Define 𝑧 = (0.2 + |E ∩ (𝑢, 𝑡]|) • log 𝑚 for convenience. For this, we will apply Lemma A.7 with 9) and ( 10) that for all 𝑢 ′ ∈ (𝑢, 𝑡], we have Φ 3𝑢 ′ -1 = Φ 3𝑢 ′ = 0 and thus 𝑔(•) takes at most 𝑚 |E∩(𝑢,𝑡 ] | many values. 9From Lemma A.7, we get:

where:

Next, we claim that we can łdropž the conditioning on 𝑓 𝐵 . For this, recall from Lemma 5.6 that the events Φ ≤3𝑡 and ∀𝐶 ∈ {𝐴, 𝐵} : f 𝐶 ∈ Rec 𝐶 (Φ ≤3𝑡 ) are equivalent. As the latter event is a combinatorial rectangle (it is of the form (f 𝐴 ∈ A) ∧ (f 𝐵 ∈ B) for some sets A, B) and the random variables f 𝐴 and f 𝐵 are independent, we get that the random variables f 𝐴 and f 𝐵 are also independent conditioned on Φ ≤3𝑡 . Next, recall that PC >ℓ < 𝑖 (f ≤𝑖 ) is a function of f 𝐴 conditioned on Φ ≤3𝑢 , and conclude that PC >ℓ < 𝑖 (f ≤𝑖 ) and f 𝐵 are also independent conditioned on Φ ≤3𝑡 allowing us to drop 𝑓 𝐵 . A similar argument allows us to drop 𝑓 𝐵 from the other min-entropy term and we get:

By Eq. ( 11) and our choice of Φ ≤3𝑢 ∉ Guess 𝑖 (𝑢), we have:

Using Eq. ( 7) and the definition of 𝑧, we get:

This together with Eq. ( 15) shows Eq. ( 14).

When Emb ℓ < 𝑖 = 𝑡: At a high level, the analysis in this case follows the popular pointer chasing lower bound of [13]. We assume 𝜏 𝑖 = 𝐴 as the argument for 𝜏 𝑖 = 𝐵 is analogous. As 𝑡 > 0, we have ℓ < 𝑖 > 0 and we get 𝜏 ℓ < 𝑖 = 𝐵. It follows that 𝜎 𝑡 = 𝐵. Let 𝑢 = 𝑡 -1. Applying the induction hypothesis on 𝑢 and ℓ < 𝑖 , we get:

By Lemma 5.4, we also have:

Thus, it suffices to show that:

For this, we shall fix an arbitrary Φ ≤3𝑢 ∉ Guess ℓ < 𝑖 (𝑢) ∪ Info 𝐴 (𝑢) and show that:

For all 𝑖 ′ ∈ ℓ < 𝑖 , ℓ ≥ 𝑖 , define the set:

Roughly speaking, 𝑆 is the set of prefixes 𝑧 that allow the parties to guess the transcript in the next interval. Recall that Emb ℓ < 𝑖 = 𝑡 means that we are currently at the end of an interval. We now show that the probability of landing in 𝑆 is small, as formalized in Eq. ( 18) below. Next, use the fact that 𝜏 𝑖 = 𝐴 and the definition of ℓ < 𝑖 and ℓ ≥ 𝑖 to conclude that

. This, together with Lemma A.11 and the fact that

(Eq. ( 17))

As such, we get that for all 𝑖 ′ ∈ ℓ < 𝑖 , ℓ ≥ 𝑖 , we have |𝑆 𝑖 ′ | ≤ 𝑚 0.44 implying that |𝑆 | ≤ 𝑚 0.45 . Next, note that as Φ ≤3𝑢 ∉ Guess ℓ < 𝑖 (𝑢), we also have by Eq. ( 11) that H

Observe from Claim 5.2 that conditioning on Φ ≤3𝑢 fixes the value of

It follows from Eq. ( 7) and Definition A.5 that

As a consequence, Eq. ( 16) follows if we show that:

Next, note from Claim 5.2 that the value of Φ <3𝑡 fixes the value of PC(f ≤ℓ < 𝑖 ) (and also of Φ ≤3𝑢 ). Thus, it suffices to fix an arbitrary Φ <3𝑡 that agrees with Φ ≤3𝑢 and for which the corresponding value of PC(𝑓 ≤ℓ < 𝑖 ) ∉ 𝑆, and show that

By Eq. ( 11), this is the same as:

Fixing such a Φ <3𝑡 , this is because of the following two claims. We omit the formal proofs of these claims, which can be found in the full version of the paper. Claim 5.10. It holds that:

Finishing the Proof

We are now ready to prove Lemma 5.1

Proof of Lemma 5.1. Recall that we are showing the lemma in the contrapositive, assuming that 𝜏 is a not subsequence of 𝜎. This means that Emb(𝑛) > 𝑇 implying by Eq. ( 6) that there exists 𝑖 ∈ [𝑛] such that 𝑖 ∈ Good(𝑇 ). Fix such an 𝑖 and apply Lemma 5.9 to conclude that Pr(E) < 1 𝑛 2 , where E is the event Φ ≤3𝑇 ∈ Guess 𝑖 (𝑇 ). We now derive Eq. (4) as follows:

Thus, it suffices to show that Pr res Π (F) = PC(F) | E ≤ 1 𝑛 2 . We show this holds under a stronger conditioning by conditioning on an arbitrary Φ ≤3𝑇 such that Φ ≤3𝑇 ∉ Guess 𝑖 (𝑇 ). Fixing such a Φ ≤3𝑇 and noting that fixing Φ ≤3𝑇 also fixes res Π (F) to some value res we get:

(Eq. ( 11) as Φ ≤3𝑇 ∉ Guess 𝑖 (𝑇 ))

≤ 𝑚 -0.5 (Eq. ( 7))

In this section, we prove Theorem 4.2. For notational convenience, we define the constant 𝜂 = 10 -5 .

A Customized Concentration Inequality

Fact 6.1. For all integers 1 ≤ 𝑘 ≤ 𝑛, we have:

Lemma 6.2. Let 𝑍 ⊆ N and 𝑛 > 0 be an integer. Also, let 𝑝 > 0 and X 1 , X 2 , • • • , X 𝑛 be random variables taking values in N. Then, if 𝛿 > 0 is such that for all 𝑖 ∈ [𝑛] and all 𝑥 1 , 𝑥 2 , • • • , 𝑥 𝑖 -1 ∈ N, we have:

Then, it holds that:

The formal proof of Lemma 6.2 is omitted for space and can be found in the full version of the paper.

Basic Definitions

Recall that 𝜂 = 10 -5 . Also recall from Section 2.2 that we consider segments of geometrically increasing lengths. These segments will be parameterized by an integer ℓ > 0. We will use 𝐿 ℓ to denote the length of segment ℓ, 𝐷 ℓ to denote the łdelayž or the łlagž before the segment starts, and 𝐶 ℓ to denote the non-bullet symbols in the pattern for this segment. We set these parameters as follows:

𝐶 ℓ = 𝜂 6 𝐿 ℓ 𝐷 ℓ = 𝜂 4 𝐿 ℓ .

(19) We also define 𝐿 ≤ℓ = ℓ ℓ ′ =1 𝐿 ℓ ′ and 𝐿 <ℓ = ℓ -1 ℓ ′ =1 𝐿 ℓ ′ . We adopt the convention that 𝐿 ≤0 = 0 and observe that all these parameters integers. Next, we define the set {𝐴, 𝐵} • to denote the set {𝐴, 𝐵} • = {𝐴, 𝐵} ∪ {•}. For 𝜌 ∈ {𝐴, 𝐵} * • , we use bull(𝜌) to denote the number of coordinates in the string 𝜌 that are equal to the łbulletž symbol 6.4 Strings With Small Pred ℓ (•) Exist Lemma 6.8. For all integers 𝑇 > 0, there exists 𝜎 ∈ {𝐴, 𝐵} 𝑇 such that for all ℓ > 0, we have:

• 𝑇 . The formal proof of Lemma 6.8 is omitted for space and can be found in the full version of the paper.

Structure of Long Subsequences

For the remainder of this section, readers may like to recall the definition of the set E 𝜎,𝜎 ′ in Eq. ( 2). We borrow the following lemma from [16]. Lemma 6.9 ( [16], Lemma 6). Let 𝑇 ′ > 0 be an integer. Also, let I be an indexing set and a collection of pairs 𝑡 ′ 𝑖 , 𝑡 𝑖 𝑖 ∈ I be given. Assume that 0 ≤ 𝑡 ′ 𝑖 < 𝑡 𝑖 ≤ 𝑇 ′ for all 𝑖 ∈ I. There exists a set I ′ ⊆ I such that the intervals (𝑡

The formal proof of Lemma 6.10 is omitted for space and can be found in the full version of the paper.

Proof of Theorem 4.2

Proof of Theorem 4.2. We define 𝜎 to be the string promised by Lemma 6.8. Thus, for all ℓ > 0, we have:

Fix an arbitrary 𝜎 ′ ∈ {𝐴, 𝐵} * such that 𝜎 is a strong subsequence of 𝜎 ′ and let 𝑇 ′ = |𝜎 ′ |. Assume for the sake of contradiction that 𝑇 ′ < 1 + 𝜂 20 • 𝑇 . As 𝜎 is a strong subsequence of 𝜎 ′ , we must have 𝑇 ′ ≥ 𝑇 + 1 and E 𝜎,𝜎 ′ = 𝑇 . From these, we conclude that 2𝑇 ≥ 𝑇 ′ ≥ 𝑇 ≥ 𝜂 -20 and E 𝜎,𝜎 ′ ≥ 1 -𝜂 and for all 𝑖 ′ ∈ 𝐼 we have that 𝜎 is a subsequence of 𝜎 ′ -𝑖 ′ . Define the following sets:

We claim that: Claim 6.11. We have:

The formal proof of Claim 6.11 is omitted for space and can be found in the full version of the paper.

Conclude from Claim 6.11 and the fact that |𝐼 | ≥ 𝑇 ′ 10 that there exists an index 𝑧 ′ ∈ 𝐼 \ 𝑗 >0 𝐼 𝑗 . We show that this leads to a contradiction. As 𝑧 ′ ∈ 𝐼 , we have that 𝜎 is a subsequence of 𝜎 ′ -𝑧 ′ . Recall that this implies that E 𝜎, 𝜎 ′ -𝑧 ′ = 𝑇 or, equivalently, Emb 𝜎, 𝜎 ′ -𝑧 ′ ,𝑇 ≤ 𝑇 ′ -1 < 𝑇 ′ . Henceforth, for notational convenience, we abbreviate Emb 𝜎, 𝜎 ′ -𝑧 ′ , • to Emb * (•) and E 𝜎, 𝜎 ′ -𝑧 ′ to E * . We also abbreviate Emb(𝜎, 𝜎 ′ , •) to Emb(•) and E(𝜎, 𝜎 ′ ) to E.

We now use the fact that 𝑧 ′ ∉ 𝑗 >0 𝐼 𝑗 to get more information about 𝑧 ′ . From Eq. ( 22), we get that 𝑧 ′ ≤ 0.999𝑇 ′ and 𝑧 ′ ∈ E. Due to Eq. ( 2), this implies that there exists 𝑧 ∈ [𝑇 ] such that Emb(𝑧) = 𝑧 ′ . We claim that:

Indeed, if not, we have from Observation 3.1 that 0.999𝑇 ′ ≥ 𝑧 ′ ≥ 𝑧 ≥ (1 -𝜂) • 𝑇 , a contradiction to 𝑇 ′ < 1 + 𝜂 20 • 𝑇 . Next, Eq. ( 22) also says that for all 0 < 𝑘 ≤ 𝑇 ′ -𝑧 ′ , we have (as the left hand side is an integer): To derive a contradiction, we claim that: Lemma 6.12. For all ℓ ≥ 0 such that 𝑧 ≤ 𝑇 -3𝐿 ≤ℓ , we have:

The formal proof of Lemma 6.12 is omitted for space and can be found in the full version of the paper.

We finish the proof of Theorem 4.2 by showing that it implies a contradiction. For this, define ℓ * = log 10 10 𝜂 4 𝑇 ′ and note that 𝑇 ′ ≥ 𝜂 -20 implies that ℓ * ≥ 5. We get from Eq. ( 19) that As we know that Emb * (𝑇 ) < 𝑇 ′ , this contradicts 𝑇 ′ < 1 + 𝜂 20 • 𝑇 . □