{'fraction_non_alphanumeric': 0.04719395089414065, 'fraction_numerical': 0.01703467310677937, 'mean_word_length': 4.0659044567433735, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 30, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Gaussian Interference Channel with Intermittent Feedback

We investigate how to exploit intermittent feedback for interference management by studying the two-user Gaussian interference channel (IC). We approximately characterize (within a universal constant) the capacity region for the Gaussian IC with intermittent feedback. We exactly characterize the the capacity region of the linear deterministic version of the problem, which gives us insight into the Gaussian problem. We find that the characterization only depends on the forward channel parameters and the marginal probability distribution of each feedback link. The result shows that passive and unreliable feedback can be harnessed to provide multiplicative capacity gain in Gaussian interference channels. We find that when the feedback links are active with sufficiently large probabilities, the perfect feedback sum-capacity is achieved to within a constant gap. In contrast to other schemes developed for interference channel with feedback, our achievable scheme makes use of quantize-map-and-forward to relay the information obtained through feedback, performs forward decoding, and does not use structured codes. We also develop new outer bounds enabling us to obtain the (approximate) characterization of the capacity region.


I. INTRODUCTION
The simplest information theoretic model for studying interference is the two-user Gaussian interference channel (IC). It has been shown that feedback can provide an unbounded gain in capacity for two-user Gaussian interference channels [1], in contrast to point-to-point memoryless channels, where feedback gives no capacity gain [2], and multiple-access channels, where feedback can at most provide power gain [3]. This has been demonstrated when the feedback is unlimited, perfect, and free of cost in [1]. Given the optimistic result obtained under this setting, a natural question arises: Can feedback be leveraged for interference management under imperfect feedback models?
There have been several pieces of work so far, attempting to answer this question. Vahid et al. [4] considered a rate-limited feedback model, where the feedback links are modeled as fixed-capacity deterministic bit pipes. They developed a scheme based on decode-and-forward at transmitters and lattice coding to extract the helping information in the feedback links, and showed that it achieves the sum-capacity to within a constant gap. The work in [5] studied a deterministic model motivated by passive feedback over AWGN channels, and [6], [7] studied the two-way interference channel, where the feedback is provided through a backward interference channel that occupies the same resource as the forward channel. [5], [6] and [7] only dealt with the linear deterministic model [8] of the Gaussian IC.
In this paper, we investigate how to exploit intermittent feedback for managing interference. Such intermittent feedback could occur in several situations. For example, one could use a side-channel such as WiFi for feedback; in this case since the WiFi channel is best-effort, dropped packets might cause intermittent feedback. In other situations, control mechanisms in higher network layers could cause the feedback resource to be available intermittently. For the feedback links, Bernoulli processes {S 1 [t]} and {S 2 [t]} control the presence of feedback for user 1 and 2, respectively. The two processes can be dependent, but their joint distribution is i.i.d. over time. We assume that the receivers are passive: they simply feedback their received signals back to the transmitters without any processing. In other words, each transmitter receives from feedback an observation of the channel output of its own receiver through an erasure channel, with unit delay. We focus on the passive feedback model as the intermittence of feedback is motivated by the availability of feedback resources (either through use of best-effort WiFi for feedback or through feedback resource scheduling). Therefore, it might be that the time-variant statistics of the intermittent feedback are not a priori available at the receiver, precluding active coding. Moreover, the availability of the feedback resource may not be known ahead of transmission, therefore motivating the assumption of causal state information at the transmitter. If the receiver has a priori information about the feedback channel statistics, it can perform active coding, in which case, the intermittent feedback model reduces to the rate-limited model of [4].
We study the effect of intermittent feedback for the two-user Gaussian IC inspired by ideas we develop for the linear deterministic IC model [8]. Our main contribution is the approximate characterization of the capacity region of the interference C. Karakus   Our result shows that feedback can be harnessed to provide multiplicative gain in Gaussian interference channel capacity even when it is unreliable and intermittent. The result can be interpreted using the picture given in Figure 1, which is depicted (for convenience) in terms of symmetric generalized degrees of freedom for the special case of symmetric channel parameters. The given GDoF curves suggest that as the feedback probability increases, the achievable GDoF also increases for all interference regimes for which perfect feedback provides any GDoF gain. One can also observe from the figure that the capacity gain from intermittent feedback, which depends on the portion of time when the feedback is active, remains unbounded, similar to the perfect feedback case.
A consequence of this result is that when the feedback links are active with large enough probabilities, the sum-capacity of the perfect feedback channel can be achieved to within a constant gap. Similarly for the linear deterministic case, the perfect feedback capacity is exactly achieved even when there is only intermittent feedback, with large enough "on" probability. In particular, under the symmetric setting, this threshold is 1/2 for each feedback link. This is also reflected in Figure 1, where the "V-curve" achievable with perfect feedback is already achievable when the feedback probability is only 1/2.
Our achievable scheme has three main differences from the previous schemes developed in [1], [4] and [5]. First, we use quantize-map-and-forward (QMF) 1 [8] at the transmitters to send the information obtained through feedback, as opposed to (partial or complete) decode-and-forward, which has been used in [1], [4], [5]. This is because when there is intermittent feedback, the transmitters might not be able to decode the other user's (partial) message, but would still need to send useful information about the interference. A similar situation arises in a relay network, where QMF enables forwarding of evidence, without requiring decoding [8]. Second, at the receivers, we perform forward decoding of blocks instead of backward decoding, which results in a better delay performance. Third, we do not use structured codes, i.e., we only perform random coding.
We also develop novel outer bounds that are within a constant of the achievable rate region for the Gaussian IC and match the achievable region for the linear deterministic IC. These outer bounds are based on constructing an enhanced channel and appropriate side-information. These are illustrated in Section VI.
Lastly, we extend these results for packet transmission channels, modeled through parallel channels which are M -symbol extensions of the original model. This can be considered as a model for OFDM and packet drops over a best-effort channel.
The rest of this paper is organized as follows. We formally state the problem and establish the notation in Section II. We present our main results in Section III and give interpretations of them. We motivate our coding scheme and explain it through an example in Section IV. We give the analysis of the coding scheme in Section V. The outer bound is developed in Section VI and Section VII concludes the paper with a brief discussion of possible extensions of the work. Many of the detailed proofs are given in the Appendices.
II. SYSTEM MODEL We consider the 2-user discrete memoryless interference channel (DM-IC) with intermittent feedback, illustrated in Figure 2. We assume Transmitter i (Txi) has a message W i intended for Receiver i (Rxi), i = 1, 2. W 1 ∈ 2 N R1 and W 2 ∈ 2 N R2 p(y 1 , y 2 |x 1 , x 2 ) Fig. 2. Two-user discrete memoryless interference channel with intermittent feedback are independent and uniformly distributed, where, for n ∈ N, [n] := {k ∈ N : k ≤ n}. The signal transmitted by Txi at time t is denoted by X i,t ∈ X i , while the channel output observed at Rxi is denoted by Y i,t ∈ Y i , for i = 1, 2. For a block length N , the conditional probability distribution mapping the input codeword to the output sequence is given by The feedback state sequence pair S := S N 1 , S N 2 have the joint distribution p (S 1,t , S 2,t ) .
and marginally, at time t, S i,t ∼ Bernoulli(p i ), for i = 1, 2, for all t and N . Note that, for any fixed time slot t, the random variables S 1,t and S 2,t are not necessarily independent, that is, the joint distribution p(S 1,t , S 2,t ) can be arbitrary. We assume that receivers have access to S strictly causally, that is, at time t, both receivers know the realization of S t−1 . At the beginning of time t, Txi observes the channel output received by Rxi at time t − 1 through an erasure channel, i.e., it receives Y i,t−1 := S i,t−1 Y i,t−1 , for i = 1, 2. Note that this is a passive feedback model, in that it does not allow the receiver to perform any processing on the channel output; it simply forwards the received signal Y i at every time slot, which gets erased with probability 1 − p i .
For random variables A and B, we use the notation A f = B to denote that A is a deterministic function of B 2 . Then our channel model implies X i,t A rate pair (R 1 , R 2 ) is said to be achievable if there exists a pair of codebooks (C 1 , C 2 ) at Tx1 and Tx2, with rates R 1 and R 2 , respectively, and pairs of encoding and decoding functions such that the average probability of error at any decoder goes to zero as the block length N goes to infinity. The capacity region with feedback probabilities p 1 and p 2 , C(p 1 , p 2 ), is defined as the closure of the set of all achievable rate pairs (R 1 , R 2 ) when S 1 ∼ Bernoulli(p 1 ) and S 2 ∼ Bernoulli(p 2 ). Sum-capacity is defined by C sum (p 1 , p 2 ) := sup {R 1 + R 2 : (R 1 , R 2 ) ∈ C(p 1 , p 2 )} .
In this work, we consider two specific channel models (that is, two specific classes of (X 1 , X 2 , Y 1 , Y 2 , p (y 1 , y 2 |x 1 , x 2 ))), described in the following subsections.

A. Linear Deterministic Model
This channel model was introduced in [8] and since then proved useful in providing insight into the nature of signal interactions many network information theory problems (see Figure 3).
We assume X i,t ∈ F q 2 , for i = 1, 2, where F 2 is the binary field. The received signal at Rxi is given by for (i, j) = (1, 2), (2,1). The channel matrices are given by H ij := S q−nij for (i, j) ∈ {1, 2} 2 , where q = max {n 11 , n 12 , n 21 , n 22 }, , where 0 is the zero vector in F q−1 2 and I q−1 is the identity matrix in F We also define, for (i, j) = (1, 2), (2, 1), The capacity region for the linear deterministic model will be denoted by C LDC (p 1 , p 2 ), while its sum-capacity will be denoted by C sum LDC (p 1 , p 2 ).

B. Gaussian Model
Under the canonical Gaussian model (see Figure 4), the channel outputs are related to the inputs through the equations 2 , are channel gains, and Z 1,t , Z 2,t ∼ CN (0, 1) are circularly symmetric complex white Gaussian noise. We assume an average transmit power constraint of P i at Txi, i.e., for any length-N codeword X N i transmitted by Txi, 1 We also define for (i, j) = (1, 2), (2,1). Note that this definition of V i,t is consistent with its definition under linear deterministic model, in the sense that it is what remains out of the channel output when the intended signal is completely cancelled. The capacity region for the Gaussian model will be denoted by C G (p 1 , p 2 ), while its sum-capacity will be denoted by C sum G (p 1 , p 2 ). We will also use the notation C sum G,p := C sum G (1, 1), denoting the sum-capacity under perfect feedback. Gaussian parallel channel is described by the equations where X i,t , Y i,t ∈ C M , i = 1, 2, are the channel input and output, respectively, at user i; Z 1,t and Z 2,t are independent and distributed with CN (0, I); and Y i,t , i = 1, 2 is the output of the feedback channel of Txi, at time t. Note that the channel gains are scalars. It should also be noted that any given time, the same feedback state variable S i,t controls the presence of feedback for all sub-channels, i.e., the feedback is present either for all M channels, or for none of them.

III. MAIN RESULTS
In this section, we present our results and discuss their consequences for both linear deterministic and Gaussian models.

A. Linear Deterministic Model
The following theorem captures our main result for the linear deterministic model.
The capacity region C LDC (p 1 , p 2 ) of the linear deterministic interference channel with intermittent feedback is given by the set of rate pairs (R 1 , R 2 ) satisfying (5)-(10).
Proof. See Section V for achievability, and Section VI for converse.
The following corollary shows that it is possible to achieve perfect feedback sum-capacity even when feedback probabilities are less than one.
Corollary 3.1. For n 12 , n 21 > 0, there exists p * < 1 such that We illustrate Corollary 3.1 through an example. Let us assume n 12 = n 21 = m, n 11 = n 22 = n, and p 1 = p 2 = p. It is easy to see that if p 1 = p 2 = 0.5, the bounds on R 1 + R 2 , 2R 1 + R 2 and R 1 + 2R 2 that involve p 1 and p 2 become redundant, and the sum-capacity does not increase beyond this point, for all (m, n).

B. Gaussian Model
We define, for any set R of rate pairs (R 1 , R 2 ) and scalar δ ∈ R, The following theorem captures our main result for the Gaussian model.
Proof. Section V proves an inner bound region R i G (p 1 , p 2 ), Section VI proves an outer bound region R o G (p 1 , p 2 ), and Appendix F shows thatC(p 1 , p 2 ) − δ 1 ⊆ R i G (p 1 , p 2 ) and R o G (p 1 , p 2 ) − δ 2 ⊆C(p 1 , p 2 ). Remark 3.1. Theorem 3.2 uniformly approximates the capacity region under Gaussian model to within a gap of 3 log 3 + 4 (p 1 + p 2 ) bits, independent of channel parameters. To our knowledge, this is the first constant-gap capacity region characterization for interference channel with noisy feedback with arbitrary channel parameters. Remark 3.2. As will be seen in the achievability proof, the proposed coding scheme achieves a smaller gap than what is given in Theorem 3.2; however, for simplicity in the achievability proof, we lower bound the achievable rate terms with computationally more tractable ones, which articifically contributes to the claimed gap. Moreover, one can optimize over the parameters of the proposed coding scheme, such as power allocation and quantization distortion, to further reduce the gap, but this issue will not be dealt with in this paper.
Theorem 3.2 allows us to characterize the symmetric generalized degrees of freedom under symmetric channel parameters, which is a metric often used to compare the capabilities of the interference channel under different settings.  Figure 5 plots the available generalized degrees of freedom with respect to interference strength for various values of p. As can be observed, as p is increased, gradually better curves are obtained. It should be noted that once p ≥ 0.5, the "V-curve" that is achieved by perfect feedback [1] is already achieved. Next, this observation will be made precise.  The perfect feedback outer bound on the sum-capacity, C sum G,p , is given in Theorem 3 of [1] as follows. The next corollary shows that when p 1 and p 2 are sufficiently large, the sum-capacity of the perfect feedback Gaussian channel can be achieved with intermittent feedback, to within a constant gap. Hence, this corollary is the Gaussian counterpart of the similar result given in Corollary 3.1, for the linear deterministic channel.
In our intermittent feedback model, erasures are symbol-wise, that is, each symbol can get erased independently of others. However, in a best-effort channel, erasures might occur on packet-level instead. In order to study this scenario, we consider the parallel channel model described by the equations (1)-(4), which is simply the M -symbol extension of the Gaussian channel, where the channel parameters are the same for each subchannel. Each extended symbol over this channel models a packet. The result in Theorem 3.2 easily generalizes to parallel channel model, as shown by the following corollary.
Remark 3.3. Although strictly speaking, the claim in Corollary 3.4 is more general than that in Theorem 3.2, the achievability and converse proofs for the scalar channel directly extend to the parallel channel without any non-trivial modification. Hence, for simplicity, we focus on the scalar case in the paper, and omit a separate proof for the parallel channel.
C. Discussion of Results 1) Feedback Strategy: Our result shows that even unreliable feedback provides multiplicative gain in interference channels.
The key insight in showing this result is using quantize-map-forward as a feedback strategy at the transmitters. This is in contrast to the schemes proposed for perfect feedback [1] and rate-limited feedback [4], which use decode-and-forward to extract the feedback information. When the feedback channel is noisy, such schemes can result in rates arbitrarily far from optimality. In order to see this, consider unfolding the channel over time, as shown in Figure 6. This transformation effectively turns this channel into a relay network, where it is known that decode-and-forward based relaying schemes can give arbitrarily loose rates. This also motivates using quantize-map-forward as a feedback strategy, which has been shown to approximately achieve the relay network capacity [8]. This observation also suggests that quantize-map-forward might be a promising feedback strategy for the additive white Gaussian noise (AWGN) feedback model of [5] in order to uniformly achieve its capacity region to within a constant gap.
It is instructive to compare the achievable rate region for the case of p 1 = p 2 = 1 with the outer bound region of the perfect feedback model of [1]. Evaluating the regionC(p 1 , p 2 ) − δ 1 with p 1 = p 2 = 1, we see that the perfect feedback bound (13) becomes redundant, and the achievable region comes within (3 + 3 log 3) bits of the outer bound region of [1] (see Appendix F for details). We note that this gap is larger than what is achieved by the decode-and-forward based scheme of [1]. This shows that uniform approximation of capacity region via quantize-map-forward comes at the expense of an additional (but constant) gap 3 . The source of this additional gap is the quantization step at the transmitters, which introduces a distortion in the feedback signal, and eventually incurs a constant rate penalty whose amount depends on the distortion level.
2) Perfect Feedback Sum Capacity with Intermittent Feedback: Corollary 3.3 shows that for any set of channel parameters, there exists a threshold p * on the feedback probability above which perfect feedback sum-capacity is achieved to within a constant gap. Although the exact closed-form expression of p * is not clean, an examination of the symmetric case (see Figure 5) reveals that in some cases it can be as low as 0.5.
The intuition behind this result lies in the fact that it takes the transmitter forward-channel resources to send the information obtained through feedback. Note that the larger p is, the larger the amount of additional information about the past reception can be obtained through intermittent feedback at the transmitters. If the amount of such information is larger than a threshold, then sending it to the receivers will limit the rate for delivering fresh information. Hence, once this threshold is reached, having more feedback resource is no longer useful. However, this property is not observed for the entire capacity region, since if one of the users transmit at a low rate, then it will have sufficient slackness in rate to forward the entire feedback information.

IV. MOTIVATION OF THE CODING SCHEME
In this section, we illustrate our coding scheme through an example over the linear deterministic channel. This example is intended to demonstrate how and why the proposed scheme works, and motivate the use of quantize-map-forward as a feedback strategy.
We consider the symmetric channel shown in Figures 7 and 8, with n 11 = n 22 = 4, n 12 = n 21 = 2, and p 1 = p 2 = 0.5, and focus on the achievable symmetric rate. In this example we will take a block length of N = 2 for illustration purposes. Although for this particular case, the probability of decoding error is large due to short block length, in general the same coding idea can be applied for a large block length, in which case arbitrarily small error probability can be achieved by taking advantage of the law of large numbers.
We focus on two blocks of transmission. At each block, the users split their messages into common and private parts. The common parts of the messages are decoded by both receivers, whereas the private part is only decoded by the intended receiver, as in Han-Kobayashi scheme for the interference channel without feedback [13]. In the first block, Tx1 sends linear combinations of its two common information symbols, a 1 , a 2 on its two common (upper) levels, and linear combinations of its private information symbols, a 3 , a 4 , a 5 , a 6 , over its private (lower) two levels over a block of two time slots. Tx2 performs similar operations for its common symbols b 1 , b 2 , and its private symbols b 3 , b 4 , b 5 , b 6 .
Note that at this point, the receivers can decode the symbols sent at their upper two levels by solving the four equations in two unknowns.
After each time slot, the receivers feed back their channel outputs, but the transmitters wait until the end of the block to collect sufficient information from feedback. We consider a particular feedback channel realization S N 1 , S N 2 = ((1, 0), (0, 1)) for illustration purposes. After the first block, each transmitter gets from feedback two linear combinations of the interfering symbols of the previous block, by subtracting their own linear combinations from the channel outputs. In the second block, the transmitters perform further linear encoding of these two linear combinations. These additional linear combinations of the interference symbols are superimposed on top of the linear combinations of the fresh common information symbols a 7 , a 8 (and b 7 , b 8 for Tx2) of the second block. On the private levels, linear combinations of new symbols a 9 , a 10 , a 11 , a 12 at Tx1 and b 9 , b 10 , b 11 , b 12 at Tx2 are sent, as in the first block.
After the second block of transmission, the receivers collect the four linear equations obtained in the lower two levels of the first block and the four linear equations obtained at the upper two uninterfered levels in the second block. It is easy to check that these eight equations are linearly independent, and hence the receivers can solve for the eight unknowns (a 3 , a 4 , a 5 , a 6 , a 7 , a 8 , b 1 , b 2 for Tx1, and b 3 , b 4 , b 5 , b 6 , b 7 , b 8 , a 1 , a 2 for Tx2).
Having decoded the private information (and interference) of the first block and the common information of the second block, the receivers next cancel the additional linear combinations of the previously decoded common information received at the lower two levels of the second block due to feedback. This means that Rx1 cancels the a 1 and a 2 symbols in the lower two levels, and Rx2 cancels the b 1 and b 2 symbols.
Since the transmitters can also cancel this information from the received feedback (because it is a function of their own symbols), the state of each terminal reduces to that in the end of the first block. Therefore, in each of the following blocks, the operation in the second block can be repeated, each time letting the receivers decode the private information of the previous block and the common information of the new block.
One caveat is that, the feedback channel realization will not be the same at each block. To address this point, we first note that the only decoding error event is when the channel realization is such that the resulting linear system in any of the receivers is not full rank. For the particular code in the example, it is easy to check that the probability of this event is zero for any feedback channel realization as long as S N i = (0, 0) for i = 1, 2. In general, for any > 0, in order to achieve a symmetric rate C sym − , Txi needs to receive feedback for at least N (p i − ) time slots at each block. This condition is ensured by law of large numbers by letting N → ∞, and arbitrarily small error probability can be achieved 4 .  Receptions enclosed in green/solid rectangles represent the channel outputs that the receivers are able to feed back; whereas those enclosed in red/dashed rectangles represent the channel outputs that gets erased through the feedback channel. a 9 + a 10 + a 11 a 10 + a 12

Round 1 Round 2
Round 2 Round 1 p 1 = 0.5 p 2 = 0.5 Fig. 8. Second block of transmissions for the example coding scheme over linear deterministic channel. The helping information sent by the interfering transmitters (a 1 , a 2 at Rx1, b 1 , b 2 at Rx2) are omitted for brevity. Note that these are already known at the receivers from previous block, and hence can be cancelled.
To find the symmetric rate achieved by this scheme, we assume the scheme is run for B blocks. At the end, each receiver will have resolved 6B − 4 information bits in 2B time slots. Letting B → ∞ gives a symmetric rate of 3 bits/time slot. Note that without feedback, a symmetric rate of at most 2 bits/time slot can be achieved. At the other extreme, it is also easy to verify from the results in [1] that symmetric capacity under perfect feedback is also 3 bits/time slot, which is in agreement with Figure 5 and Corollary 3.1.
This example also serves to demonstrate why we perform quantize-map-forward instead of decode-and-forward as a feedback strategy. In general, to achieve the symmetric capacity, Tx2 needs to send linear combinations of N information symbols on its common levels, while Tx1 receives 2N p 1 of these linear combinations on the average. Hence, if p 1 < 0.5, Tx1 will not be able to decode the interference of the previous block. Instead, Tx1 performs a linear mapping of the received feedback information, which turns out to achieve the symmetric capacity.
Finally, we point out that decoding in this scheme is sequential, i.e., the receiver decodes the blocks in the same order they are encoded 5 . This is in contrast to earlier feedback coding schemes proposed for interference channel, which perform backward coding. The obvious advantage of using sequential decoding is better delay performance, since the receiver does not need to wait for the end of the entire transmission to start to decode.

V. ACHIEVABILITY PROOF
In this section, we describe the coding scheme in detail and derive an inner bound R i G (p 1 , p 2 ) on the rate region.

A. Overview of the Achievable Strategy
The main idea of the coding scheme is the same as the one presented for the example in Section IV. However, it substantially generalizes the example scheme in order to account for possible channel noise, different interference regimes and an arbitrary target rate point in the achievable region.
The scheme consists of transmission over B blocks, each of length N . At the beginning of block b, upon reception of feedback, transmitters first remove their own contribution from the feedback signal and obtain a function of the interference and noise realization of block b − 1. This signal is then quantized and mapped to a random codeword, which will be called the helping information. Finally, a new common codeword, which is to be decoded by both receivers, and a private codeword, to be decoded by only the intended receiver, are superimposed to the helping information, and transmitted.
The decoding operation depends on the desired rate point (see Figure 10). To achieve the rate points for which the common component of the message is large, the receiver simply performs a variation of Han-Kobayashi decoding [13], i.e., it decodes the intended information jointly with the common part of the interference. Note that this does not make use of the helping information.
To achieve the remaining rate points, the helping information is used. For weak interference, at block b, we assume that the receiver has already decoded the intended common information of block b − 1. After receiving the transmission of block b, the receivers jointly decode the intended private information and the interference of block b − 1 jointly with the common information of block b, while using the helping information sent at block b as side information. For strong interference, the roles of intended common information and the interfering common information get switched.
Next, we present a detailed description of the coding scheme and proof of achievability.

B. Codebook Generation
, and X if are the alphabets for the symbols X ie , X ic , X ip , and X if , respectively.

C. Encoding
Encoding is performed over blocks (indexed by b) of length N . See Figure 9 for a system diagram. At the beginning of block b, Txi receives the punctured feedback signal containing information about the channel output in block b − 1, where the multiplication is element-wise. Upon reception of Y N i , Txi first removes its own contribution from the feedback signal to obtain . For linear deterministic model, this is done by , whereas for Gaussian model, it can be obtained by where T (N ) denotes the -typical set with respect to the distribution p( v j )p(u i | v j ), and p( v j ) is induced by the channel and the input distributions. If such an index Q i (b) has been found, the codeword X N ie (Q i (b)) that has the same index is chosen to be sent for block b. If there are multiple such indices, the smallest one is chosen. If no such index is found, the quantization index 1 is chosen.
Next, the message W i (b) ∈ 2 N Ri to be sent at block b is split into common and private components ( is chosen from the respective codebooks. Finally, the using the symbol-wise maps x if (·, ·) and x i (·, ·), we obtain the codewords where the functions are applied to vectors element-wise. X N i (b) is sent at Txi over N channel uses.

D. Decoding
The message indices for common and private messages, and the quantization indices of Txi at block b will be denoted by m i (b), n i (b), and q i (b), respectively. When there are two quantization indices to be decoded from the same user, the second one will be denoted with q i (b).
In order to describe the decoding process, we need to introduce some notation. Define the following sequence of sets: is the set of quantization indices of Txi that are jointly typical with the interference of the previous round. If any of the indices (q j , m j ) is known, we will suppress the dependence to that index, e.g., if both are known, we simply denote where X N jf (b − 1) refers to the codeword corresponding to the known message indices. We assume that the set B Note that due to random codebook generation, K i (b), i = 1, 2, are random variables. The following lemma shows that K i (b) is almost surely bounded for sufficiently large N .
Lemma 5.1. For any > 0, there exists a block length N , and a quantization scheme such that Proof. See Appendix A.
Lemma 5.1 suggests that for each interference codeword, there is a constant number of plausible quantization codewords, for sufficiently large block length (to see that κ i is a constant independent of channel parameters, refer to Appendix C). This means that the cost of jointly decoding the quantization indices together with the actual messages is a constant reduction in the achievable rate, which will be a useful observation in deriving the constant-gap result.
We also define C i = κ i +2κ j , for (i, j) = (1, 2), (2, 1). The reason for this particular definition will become clear in the error analysis. Intuitively, C i represents the rate cost associated with performing quantization to forward the feedback information, which introduces distortion. However, as we will show later in the proof, the upper bound given in Lemma 5.1 can be evaluated as a constant independent of channel parameters.
Given an input distribution, Rx1 is said to be in weak interference if I(X 2 ; Y 1 |X 1 ) ≤ I(X 1 ; Y 1 |X 2 ), and in strong interference otherwise. These regimes are defined similarly for Rx2.
Decoding operation depends on the interference regime and the desired operating point (R 1 , R 2 ). In order to describe the relevant regimes of operating points, we define for (i, j) = (1, 2), (2,1). In what follows, for clarity, we will focus only on Rx1. The operations performed at Rx2 are similar.
If, for the desired operating point, R 1c > I w1 , where I w1 is as defined in (16), the helping information is not used, and a slight modification of Han-Kobayashi scheme is employed. Otherwise, the helping information is used to decode the information of block b − 1. We describe the decoding for the two cases below.
where the known message indices are suppressed. If the receiver can find a unique collection of such indices, it declares them as the decoded message indices ; otherwise it declares an error. After decoding, given the knowledge of X N 1 (b), Rx1 reconstructs X N 1e (b + 1) by imitating the steps taken by Tx1 at the beginning of block b + 1, thereby maintaining the assumption that X N 1e (b) is known at the beginning of block b. Further, note that X N 2e (b) is not uniquely decoded, hence in block b + 1, it will still be jointly (but still, non-uniquely) decoded with the variables of that block. We resort to non-unique decoding of this codeword since unique decoding imposes an additional rate constraint on the helping information, thereby limiting the amount of rate enhancement it can provide.
If a unique collection of such indices exists, then these are declared as the decoded message indices . Otherwise, an error is declared.
is suppressed, since these indices correspond to messages that have already been decoded.
In words, the decoder jointly decodes the private information and the interference of block b − 1 jointly with the helping information and common information from block b.
Note that non-unique decoding is performed for X N 1e (b), but we have assumed that X N 1f (b − 1) and thus, X N 1e (b − 1) is uniquely known at the beginning of block b. In order to maintain this assumption for the next block, X N 1e (b) is reconstructed at Rx1. To achieve this, given the knowledge of X N 1 (b−1), and the quantization codebook, Rx1 imitates the operations performed by Tx1 at the beginning of block b.
2) Strong Interference (I(X 2 ; Y 1 |X 1 ) > I(X 1 ; Y 1 |X 2 )): As in the weak interference case, decoding depends on the operating point. For R 2c < I s1 , where I s1 is as defined in (17), helping information is used, otherwise, it is not used.
R 2c ≥ I s1 : The operations performed are identical to those for the case of R 1c ≥ I w1 under weak interference.
, and X N 2c (b − 1) are known at Rx1 at block b. To decode, Rx1 attempts to find unique indices (m 1 If a unique collection of such indices exists, they are declared as the decoded message indices Otherwise, an error is declared. Using the information of X N 1 (b−1), Rx1 can now uniquely reconstruct X N 1e (b−1) by following the steps taken by Tx1 at the beginning of block b.

E. Error Analysis
Without loss of generality, we only consider the error events occurring at Tx1 and Rx1. All arguments here will be applicable to the other Tx-Rx pair. We define the following decoding error events at Rx1, for block b and block length N : The overall decoding error events at Rx1 is given by We first prove that in order to find the rate achieved after transmission of B blocks, it is sufficient to focus on the error events at an arbitrary block b. Without loss of generality, consider the error event D F B,w (N ). Assume that, after B blocks of transmission, the effective rate achieved by Txi isR i (Note that at the end of block B, some of the information pertaining to block B is still undecoded), which can be lower bounded byR i ≥ B−2 B R i , by ignoring the partial information decoded in the first block and the last one. We can also upper bound the overall probability of error by for an arbitrary block b, where the second line follows by the fact that the encoding and decoding processes are identical in each block, and we made a definition in the last line for brevity 7 . Setting B = N = N , we see that for any N , an error probability less than N P (D F B,w (b, N )) can be achieved with rate N −1 N R i . Therefore, in order to show that rate R i is achievable, it is sufficient to show that N P (D F B,w (b, N )) → 0 as N → ∞. Using the same arguments, one can show the same result for D F B,s (N ) and D N F B (N ), and define D F B,s (b, N ) and D N F B (b, N ) similarly. Now we analyze the weak and strong interference regimes separately. 1) Weak Interference: The following lemmas characterize the rate constraints for reliable communication with Rx1 for feedback and non-feedback strategies, respectively, under weak interference.
Proof. See Appendix B.
2) Strong Interference: The following lemmas give the rate constraints for the feedback and non-feedback modes under strong interference at Rxi.

F. Rate Region Evaluation
In this subsection, we first explicitly derive the set of achievable (R 1 , R 2 ) pairs for linear deterministic and Gaussian models, from the results of the previous subsection.
We first find the conditions for decodability at Rx1 under weak interference. Recall that feedback mode is used at Rx1 only if (21) is satisfied; otherwise Han-Kobayashi decoding is performed. If we define R := (R 1c , R 2c , R 1p ), and then the set of rate points R w that ensure decodability at Rx1 under weak interference contains is the complement of the set R w d . Therefore, the rate constraints for decodability at Rx1 for the described strategy for weak interference are given by (22)-(25) and (27) (2,1), consistent with the distortion constraints.
One can perform the same line of arguments as in the case of weak interference to show that the rate constraints for decodability at Rx1 for strong interference are given by (32)-(35) and (37)-(39), for all joint distributions (2,1), consistent with the distortion constraints.
Next, we consider linear deterministic and Gaussian models separately, and derive the achievable rate regions explicitly for both cases.
1) Rate Region for Linear Deterministic Model: To obtain the achievable rate region, we first evaluate the mutual information terms with specific input distributions. In particular, we choose the distributions and mappings denotes uniform distribution over the set A. Evaluating the mutual information terms of the previous subsection with this set of distributions, and applying Fourier-Motzkin elimination (see Appendix C for details), we obtain the rate region given in (5)-(10).
2) Rate Region for Gaussian Model: Now we evaluate the rate constraints obtained in the previous section, and obtain the final achievable rate region. Assuming available power P i at Txi, we assign the following input distributions, for (i, j) = (1, 2), (2, 1): where D i > 0 are the distortion parameters. Using these input distributions, and applying Fourier-Motzkin elimination (See Appendix C for details), we can show that the rate region (79)-(81), given in Appendix C, is achievable.

VI. CONVERSE PROOF
We now prove an outer bound region that exactly matches the region given in (5)-(10), and is within a constant gap of the region in (12)-(15).
The main idea between the novel bounds on R 1 and R 2 is based on a genie argument, where the receivers are provided with side-information about the messages. The bounds on R 1 + R 2 , 2R 1 + R 2 and R 1 + 2R 2 are proven through a channel enhancement technique, resembling the one used for the multiple-access channel in [16].
A. Bounds on R 1 and R 2 Since any outer bound for perfect feedback is also an outer bound for intermittent feedback, we have the perfect feedback bound for linear deterministic model, and the bound for Gaussian model, for (i, j) = (1, 2), (2, 1), which are both proved in [1]. Next, we prove a novel bound for both models.
Without loss of generality, we focus on the bound on R 1 . In order to prove the novel bound on R 1 , the main idea is to provide W 2 , V N 1 as side-information to Rx1. The intuition behind this particular choice is revealed when we consider the interference regime and operating point in which this bound is active. First, due to the structure of the capacity region, this bound is relevant only when the message (i.e., the rate) of the interfering user is small enough. Hence, for that regime, W 2 does not carry too much information, and thus providing this to Rx1 still results in a tight outer bound. Second, note that this bound is only active in the strong interference regime, where feedback from Rx2 to Tx2 creates an alternative path for the transmission of W 1 . Therefore, by forwarding this information, Tx2 indeed provides the information contained in V N 1 to Rx1.
[+] Fig. 11. The enhanced channel for Gaussian model. The block [+] is a conditional adder, which outputs the sum of the other two inputs if S i = 0, and outputs the two inputs separately otherwise.
Based on this idea, we prove the bound for linear deterministic model in Appendix D, and the bound for the Gaussian model in Appendix E, for (i, j) = (1, 2), (2, 1).

B. Bounds on
We have the perfect feedback outer bounds for linear deterministic model, and for Gaussian model, for (i, j) = (1, 2), (2, 1). Next, we prove novel outer bounds on the capacity region. In order to prove these bounds, we first define a notion of enhanced channel. Considering our achievable scheme, feedback can be interpreted as a mechanism for the receivers to separate the interference and the intended signal, to the extent allowed by the erasure probability in the feedback channel. In the weak interference regime, this allows the receiver to cancel the interference. In the strong interference regime, through the alternate path created by the interfering user, it allows the reception of additional information about the intended message. Therefore we consider an enhanced channel where the receivers observe the interference and the intended signal individually whenever the feedback is available, and their sum otherwise. In addition to this enhancement, we provide Rxi with the side-information of V N i as well, as was done in [17]. To make this more precise, we consider the two models separately. 1) Linear Deterministic Model: We define the enhanced linear deterministic channel with intermittent feedback by the following equationsY for (i, j) = (1, 2), (2, 1), whereY i is the channel output of the enhanced channel at Rxi, Y i is the channel output of the original channel, and X i and V j are as defined for the original channel. The output of the feedback channel is given by Y i = S i Y i , i.e., the same as the original channel. Note that any scheme that achieves arbitrarily small error probability in the original channel can also achieve arbitrarily small error probability for the enhanced channel, using the fact that Y i = H ii X i + V j . This means that the capacity region of the original channel is a subset of that of the enhanced channel, and we can derive an outer bound for the enhanced channel instead.
It is easy to see that this enhancement is equivalent to providing the Rxi with V N 2 , since for time slots where S i = 1, Rxi can use this information to individually obtain the interference and the intended symbol.
Using the channel enhancement technique, we arrive at the following outer bounds on the capacity region of the linear deterministic interference channel with intermittent feedback, which are explicitly proved in Appendix D.
2) Gaussian Model: Next, we extend the enhanced channel idea to the Gaussian model. In this case, while splitting the interference and the intended signal, we also split the noise evenly between these two variables (see Figure 11). Specifically, we consider the channel defined by the equations for (i, j) = (1, 2), (2, 1), whereY i is the output of the enhanced channel, and with Z ij , Z ii are independent and distributed with CN 0, 1 2 , and we defineZ i = Z ii + Z ij . The output of the feedback channel at Txi is given by S iȲi = S i · (Y ii + Y ij ), i.e., the same as the original channel. It is worth noting that unlike the linear deterministic case, this enhancement is not equivalent to providing Rxi with V N j , since giving this side-information allows the receiver to completely cancel the noise for some time slots, resulting in an infinitely loose bound.
Let C e (p 1 , p 2 ) denote the capacity region of the enhanced channel. The next lemma shows that the capacity region of the enhanced channel indeed dominates the original one.
Proof. The proof has two steps. First, we consider an intermediate channel, with capacity region C i (p 1 , p 2 ), and the channel output at Rxi is given by for (i, j) = (1, 2), (2, 1), whereZ i = Z ii + Z ij is the sum of two independent CN 0, 1 2 random variables as in the enhanced channel. SinceZ i and Z i (the noise in the original channel) have the same probability distribution and are both i.i.d. processes across time and across users, the joint distribution of the channel p(y 1 , y 2 |x 1 , x 2 ) is identical for both channels, and hence they have the same feedback capacity region, i.e., C i (p 1 , p 2 ) = C G (p 1 , p 2 ).
Next, comparing the intermediate channel and the enhanced channel, we note that any rate pair (R 1 , R 2 ) achievable in the intermediate channel is also achievable for the enhanced channel using the same pair of codes, using the fact thatȲ i = Y ii +Y ij . Therefore, C i (p 1 , p 2 ) ⊆ C e (p 1 , p 2 ), which completes the proof. Remark 6.1. We note that a similar channel enhancement technique has been applied before by Khisti and Lapidoth [16], for Gaussian multiple-access channel with intermittent feedback. In that work, the variances of the random variables Z ii and Z ij are not fixed, but are arbitrary, subject to the constraint that they sum to one. Although one can optimize over the noise variances in order to obtain the tightest bound, this only results in a small and constant improvement. Hence, for simplicity, we stick to the fixed variance of 1 2 for the noise variables of the enhanced channel. Using Lemma 6.1, we can instead prove outer bounds for the enhanced channel. In Appendix E, we prove the following bounds.

VII. DISCUSSION AND EXTENSIONS
We considered the interference channel with intermittent feedback, and derived an approximate characterization of the capacity region under Gaussian model, as well as an exact characterization for the linear deterministic case. The result shows that even intermittent feedback provides multiplicative gain in capacity in interference channels. The achievability result was based on quantize-map-forward relaying at the transmitters, and the outer bound result was based on a channel enhancement technique.
In this paper, we considered short messaging, i.e., a new message is sent at every block of transmission. An alternate approach one could try is long messaging, where the transmitters send codewords describing the same message at every block, and the receivers jointly decode all blocks to recover the message. The clear advantage of short messaging approach is better delay performance, since each message is decoded immediately after the transmission of the corresponding block, instead of waiting for the end of the entire transmission. However, combined with forward decoding, the rate region achievable by this strategy cannot approximate the entire capacity region by itself, as can be seen from the results of Section V; we need to take the union with Han-Kobayashi rate region to approximate the entire capacity region. This is because while decoding block b, part of the message of block b + 1 is jointly decoded by treating the interference of block b + 1 as noise, which limits the rate in certain operating points. Hence, long-messaging approach would remove the need for taking union with Han-Kobayashi region and simplify the proof, since all blocks are jointly decoded. Such an approach has been taken in [18] to derive an inner bound on the capacity region of interference channels with generalized feedback, which overlaps with the capacity region (5)- (10) for the special case of linear deterministic IC with intermittent feedback.
The extension to parallel channels is carried out for the special case of identical subchannels in this work. An important generalization can be the case where the channel gains of the subchannels are not necessarily the same. The main obstacle in generalizing our achievable scheme to this case is that it distinguishes the cases of weak and strong interference, although such a separation is not possible for vector channels. Again, long-messaging can be a strategy to circumvent this issue, since it removes the need for making such a distinction between weak and strong interference regimes [18], albeit at the cost of a much larger delay.
Another important extension could be to the additive white Gaussian noise (AWGN) feedback model of [5]. Since this model assumes passive feedback as well, our quantize-map-forward based scheme can be directly applied to to this channel model. The results of this paper indicate that quantize-map-forward, as a feedback strategy, might be a promising candidate as an approximately-capacity-achieving scheme for AWGN feedback model. However, this investigation is not the focus of this paper, and is left as future work.
[13] T. S. Han and K. Kobayashi, "A new achievable rate region for the interference channel," IEEE Transactions on Information Theory, vol. Choose > 0. We suppress the dependence of variables on block index b for simplicity. Consider, for (i, j) = (1, 2), (2, 1), where (a) is due to independence of the indicator variables, and we have defined Hence, there exists N 1 such that for all N > N 1 , for some δ( ) with δ( ) → 0 as → ∞. Define η := 2 N ri 2 −N [I(X jf ;Ui)−δ( )/3] (2 N δ( )/3 − 1), and the sequence of events Borel-Cantelli lemma [20] states that if ∞ n=1 P (E n ) < ∞, then P (E n infinitely often) = 0. Then consider where (a) follows by Chebyshev's inequality, and (b) is because exponentially decaying series converge, and r i > I( V j ; U i ) ≥ I(X jf ; U i ) where the first inequality is by covering lemma [19], and the second is by data processing inequality (recall that X jf − V j − U i is a Markov chain). Therefore, with probability one, there exists a finite integer N 2 ≥ N 1 such that for all N ≥ N 2 , Choosing r i = I( V j ; U i ) + δ( )/3, taking the logarithm of both sides, and dividing by N , we get the desired result.

APPENDIX B PROOFS OF LEMMAS 5.2, 5.3, 5.4 AND 5.5 A. Notation
We will often suppress the dependence on block index b and block length N for brevity. For any given set of message indices (m 1 , n 1 , m 2 ), define the following events, with a little abuse of notation T (m 1 , n 1 , m 2 ) := {∃ (q 1 , q 2 , q 2 ) s.t. (19) holds for theindices (m 1 , n 1 , m 2 , q 1 , q 2 , q 2 )} , T (m 1 , n 1 , m 2 , q 1 , q 2 , q 2 ) := {(19) holds for the indices(m 1 , n 1 , m 2 , q 1 , q 2 , q 2 )} We also define the following quantization error event at Txi for (i, j) = (1, 2), (2, 1), and E := E 1 ∪ E 2 . Without loss of generality, we assume that the correct message and quantization indices correspond to the index 1, i.e. (W 1c , W 1p , W 2c , Q 1 , Q 2 ) = (1, 1, 1, 1, 1) for all blocks. We introduce the notation An arbitrary element of the setB i (b) will be denoted withq i , orq i . In this analysis, we focus on an arbitrary block b, but we will also need to refer to variables from block b − 1. The variables associated with block b − 1 will be represented with a caron notation when in single letter form. For example, whileX 2e is the single letter form for X N 2e (b − 1), X 2e is the single letter form for X N 2e (b). The feedback state pair S = (S 1 , S 2 ) is assumed to be conditioned upon in all the mutual information terms (since the receivers have access to this information causally), but will be omitted for brevity.

B. Claims
In this subsection, we will prove two simple claims that will be useful in bounding the probability of decoding error.
Claim B.1. Let A k , k = 1, 2, ... be a sequence of i.i.d. events. Let S ⊂ N be a random subset of natural numbers (not necessarily independent from the events A k ) such that |S| ≤ M a.s. for some real number M , and P (A k |S) = P (A m |S) a.s. for all (k, m) pairs. Then for an arbitrary j. Proof.
where (a) follows by the fact that P (A k |S) is the same for all k. Proof.
where D (P ||Q) is the relative entropy between probability distributions P and Q.

C. Proof of Lemma 5.2
We will show that there exists a sequence of codes such that P (D F B,w ) → 0 exponentially, if the given rate constraints are satisfied, which implies the claimed result. The probability of the decoding error event D F B,w can be bounded by If we choose the rates of the quantization codebooks such that r i > I( V j ; U i ), for (i, j) = (1, 2), (2, 1), by covering lemma [19], P (E 1 ) , P (E 2 ) → 0. Therefore, it is sufficient to show that P (D F B,w |E c ) vanishes if the conditions in the lemma are satisfied. The decoding error event D F B,w can also be expressed as the following union of events.
Using the union bound on (63), probability of decoding error conditioned on quantization success can be bounded by Note that conditioned on successful quantization, the relevant random variables are distributed i.i.d. over time according to the joint distribution Next, we bound the error terms one by one. In what follows, joint typicality is sought with respect to the joint distribution in (65). The first term is bounded by P (T c (1, 1, 1)|E c ) < by law of large numbers. The second error term in (64) can be bounded as follows.
• (b) follows by union bound, • (c) follows by Claim B.1, where the upper bound on the size of theB i sets for sufficiently large N is given by Lemma 5.1, • (d) follows by packing lemma and Claim B.2, • (e) is by manipulating the mutual information terms using the dependence structure of the involved variables (see Figure 12), • (f) is by upper bounding each of the eight terms with the same bound, using chain rule and non-negativity of mutual information. Next, we bound the term P (T (1, n 1 , m 2 )|E c ). We apply steps (a)-(d), which are also applicable here, to obtain the following.
where (e) is by upper bounding the first, third, fourth and fifth terms with the first term in (j), and the rest of the terms with the second; (f) is by rearranging the mutual information terms using chain rule and the fact that the distribution of variables is the same for each block. The conditioning onX 1f is because the messages corresponding to this variable has already been decoded in the previous block. In order to bound the term P (T (1, n 1 , 1)|E c ) in (64), we note that the the joint distribution (65) has a similar structure with respect to X 1c andX 1p , with the following mapping between random variableš Therefore, one can perform the steps (a)-(f) for the third error term as well, by switching the variables as above, to obtain the following bound P (T (1, n 1 , 1 We have dropped the U 1 variable from the mutual information term for the sake of simplicity in evaluating the rate region, since its contribution is small. In the final step, we used the fact that the distribution of variables is the same for each block. We can obtain the following bounds for each error term in a similar way, by exploiting the structure of the joint distribution as done above and noting that the steps (a)-(f) are applicable with an appropriate mapping between the variables. Using these bounds in (64), it is easy to see that if the following are satisfied, then P (D F B,w |E c ) → 0 as N → ∞ (Note that the bounds on R 1p + R 1c and R 1c + R 2c are redundant, as they can be expressed as a sum of other bounds), The rate constraint on R 1p + R 2c provided in the lemma is slightly stricter, which allows us to show the redundancy of some of the bounds obtained later.

D. Proof of Lemma 5.4
We will show that there exists a sequence of codes such that P (D F B,s ) → 0 exponentially, if the given rate constraints are satisfied, which implies the claimed result.
Similar to the case of weak interference, choosing the quantization rates such that r i > I( V j ; U i ), for (i, j) = (1, 2), (2, 1), probability of decoding error can be bounded by Note that conditioned on successful quantization, the relevant random variables are distributed i.i.d. over time according to the joint distribution Next, we bound the error terms one by one. In what follows, joint typicality is sought with respect to the joint distribution in (71). The first term is bounded by P (T c (1, 1, 1)|E c ) < by law of large numbers. Now we take the third term, which is bounded as follows.
Using these bounds in (70), we see that if the conditions in the lemma are satisfied, P (D F B,s |E c ) → 0 as N → ∞.
E. Proof of Lemmas 5.3 and 5.5 Extending the notation defined in the first subsection, we define T (m 1 , n 1 , m 2 , q 2 ) := {(18) holds for the indices (m 1 , n 1 , m 2 , q 2 )} We will show that there exists a code such that P (D N F B ) → 0 exponentially, if the given rate constraints are satisfied, which implies the claimed result. The decoding error event D N F B can be expressed as follows.
Similar to the previous proofs, choosing r i > I( V j ; U i ) ensures quantization success with high probability. Then since where N → 0 as N → ∞. Note that the conditions in both lemmas are sufficient to ensure P (D N F B |E c ) → 0 as N → ∞.
In order to find the set of achievable (R 1 , R 2 ) points, we first note that E i ≥ G i and C i ≥ G i , and hence the bounds E i and C i are redundant. Considering the remaining bounds for (i, j) = (1, 2), (2, 1), noting that F i ≤ A i + B i , and applying Fourier-Motzkin elimination, we find that the set of (R 1 , R 2 ) points that satisfy the following are achievable.

APPENDIX D PROOFS OF OUTER BOUNDS (52), (56), (57), AND (58)
In this section, we prove the outer bounds for the linear deterministic channel, based on the ideas presented in Section VI. We first prove four claims that will be useful in the main proof. By symmetry, it is sufficient to prove (57). To prove this bound, we consider two copies of Rx1, where one of the copies are enhanced as decribed in Section VI, while the other one is provided with the output of the original channel. The only copy of Rx2 receives the enhanced channel output as well. We would like to prove a sum rate bound for this three-receiver channel. By Fano's inequality, where (a) is by definition, (b) is due to Claim D.1. The other holds similarly.
where (a) follows by the fact that X 1,t Similarly, (c) follows since V 1,t f = (X 1,t , S t ). Now, the two equalities in the claim can be easily obtained from (b) and (c) respectively, by removing X t 1 from the conditioning by virtue of Claim D.1, and using chain rule.

APPENDIX E PROOFS OF OUTER BOUNDS (53), (59), (60), AND (61)
In this section, we prove an outer bound region for the enhanced channel defined in Section VI.

A. Notation
We defineV for (i, j) = (1, 2), (2, 1), whereV i = Y ji + Z jj = h ji X i +Z j , and For any random vector E N , we define for i = 1 or 2. Note that in vector form, this notation omits any reference to user index i for the sake of brevity. That is, although it is not clear whether E (t) is defined with respect to S 1 or S 2 , in the proof this will be clear from the context. For instance, Y are defined with respect to S 1 , since these variables refer to signals that pass through the feedback channel controlled by S 1 . The partial average power for Txi, P We focus on the case (i, j) = (1, 2). By Fano's inequality, • (c) is because Z 1,t is independent from all past signals and messages, • (d) is because W 1 − X 1,t − V 1,t is a Markov chain, hence conditioned on X 1,t , V 1,t is independent from W 1 and all the other past signals, • (e) is because given (S 2,t , X 1,t ), V 1,t is independent from all the other variables in the conditioning, In this section, we exclusively focus on the enhanced channel defined in Section VI. By Fano's inequality.
Let us take one term from (82).
where (a) follows by (with a slight abuse of notation) decomposingY N 1 into Y M1 11 , Y M1 12 for time slots where S 1,t = 1, and intoȲ L1 1 for time slots for which S 1,t = 0. The other term in (82) can be bounded similarly. Let us take one term from (84).
where (b) follows by Lemma E.6, (c) follows by chain rule, (d) follows by the fact that for a given time slot t, the involved noise terms are independent from each other and fromV 2,t ; and (e) is because the signals up to time t − 1 are independent from the noise at time t, and because noise processes are i.i.d. The other term in (84) can be bounded similarly.
Putting everything together, we have Let us combine (85) and (88).
Similarly, we combine (86) with (87) to obtain the same expression with user indices swapped. Plugging these back, we get We use Lemmas E.3, E.4, E.7 and E.8 to bound each of these terms, and use the fact that noise distribution is Gaussian to obtain the desired bound.
D. Proof of the Bounds (60) and (61) We excelusively focus on the enhanced channel, defined in Section VI. By symmetry, it is sufficient to prove (60). In addition to the enhanced interference channel in the case of sum rate bound, we consider an additional copy of Receiver 1, who always receivesȲ 1 (i.e., as in the original channel). The feedback signal of Tx1 is still given by S 1 ·Ȳ 1 , i.e., the same as the original channel. We would like to prove a sum rate upper bound on this new channel.
By Fano's inequality, The first mutual information term in (89) can be bounded as follows where (a) follows by the fact that X 1,t f = W 1 ,Ȳ t−1 1 , S t−1 and by subtracting X 1,t fromȲ 1,t . Let us consider the second mutual information term from (89).
for time slots where S 2,t = 1, and toȲ L2 2 for time slots where S 2,t = 0, and by Lemma E.6. (b) is because conditioning reduces entropy and by chain rule. (c) is because for a given time slot t, the noise terms involved are independent from each other and fromV 1,t . (d) is because conditioning reduces entropy and the noise processes are i.i.d., and because the noise terms are independent from the signals up to time t − 1.
Next, we consider the third mutual information term from (89).
where (a) follows by the fact that Z M1 , S t−1 . In (c), the first two terms are upper bounded using the fact thatY t−1 , and that conditioning reduces entropy. The noise terms are obtained by subtracting X 1,t and X 2,t fromY 1,t andV 1,t , and using the fact that noise variables at time t are independent from the variables up to time t − 1. (d) is because conditioning reduces entropy and because noise processes are i.i.d.
Putting everything back together, we have Using Lemma E.3, E.4, E.5, E.7, E.8 and E.9 to bound each of these terms, we get the desired bound.

E. Lemmas
In this subsection, we prove the lemmas that have been used in the proofs of the previous subsections.
Note that and by the definition of the channel, hence the result follows by induction on t. (a) follows because Y t−1 where (a) follows by introducing a time-sharing variable Q uniformly distributed between 1 and N , (b) is by defining Y i := Y i,Q , X i := X i,Q and V i := V i,Q . (c) follows by the fact that choosing jointly Gaussian input distribution with correlation coefficient ρ = 0 for p(x 1 , x 2 ) maximizes the given conditional differential entropy. Proof.
where (a) is by introducing a uniformly distributed time-sharing random variable Q, and (b) is by definingY i =Y i,Q ,V i =V i,Q and X j = X j,Q . (c) follows by the fact that choosing jointly Gaussian input distribution with correlation coefficient ρ = 0 for p(x 1 , x 2 ) maximizes the given conditional differential entropy.

APPENDIX F GAP ANALYSIS
In this section, we give upper bounds for the gap terms δ 1 and δ 2 from Theorem 3.2. We also compare our achievable region with the outer bound of [1] for the case p 1 = p 2 = 1.
A. Bounding δ 1 We will show that, each of the bounds (79), (80), and (81) are within a constant gap of the region given in (12)-(15). Without loss of generality, we focus on the case (i, j) = (1, 2), and start with the first bound in (79).
By symmetry, we can show that when INR 2 > SNR 2 , Next we consider the only remaining case of where in (a), we used the fact that the function log x+a x+a+b is monotonically increasing in x, for x, a, b > 0. Finally, we consider the bound (81). Again, we distinguish the cases INR 2 > SNR 2 and INR 2 ≤ SNR 2 . For the former case, For the case INR 2 ≤ SNR 2 , where in (a), as before, we used the fact that the function log x+a x+a+b is monotonically increasing in x, for x, a, b > 0. By symmetry, similar gaps apply to the case (i, j) = (2, 1). Now, we can upper bound δ 1 by noting that it cannot be larger than the maximum of the gaps found above (after proper normalization, e.g., the gap found for the bound on R 1 + R 2 is divided by 2, and the one on 2R 1 + R 2 is divided by 3). Hence, using the fact that C i = 2p j + p i and κ i = p i , we find δ 1 < 2 log 3 + 3 (p 1 + p 2 ) bits.

B. Bounding δ 2
In order to bound δ 2 , we compare the bounds obtained in Section VI with the bounds (12)-(15) one by one. Without loss of generality, we focus on (i, j) = (1, 2), and begin with the first bound in (12).
Next, we consider the second bound in (12), and note that (53) = (12) R , where (12) R refers to the right-hand side of the minimization in (12). We now consider the bound (13).
(13) = log 1 + In order to bound δ 2 , we note that it cannot be larger than the maximum of the gaps found above, after normalization as done with bounding δ 1 . Hence, we find δ 2 < log 3 + p 1 + p 2 bits.

C. Comparison with Suh-Tse Outer Bound
In this subsection, we compare our inner bound for the case p 1 = p 2 = 1 with the perfect feedback outer bound of [1]. Looking at the region (12)-(15), we see that if we set p 1 = p 2 = 1, then the bounds (14) and (15) become redundant, and the region reduces to the outer bound region of [1], with the following differences: • The outer bounds in [1] are parameterized by the parameter ρ, which captures the correlation between the symbols of two users. In the region (12)-(15), supremum values over all possible values of ρ is given. • The bounds in (12)-(15) do not contain beamforming gain terms 2ρ √ SNR i · INR i , which appear in the outer bounds of [1]. It is easy to see that the first item does not result in a rate penalty, while the second one gives a penalty of log 3 since (12) L = log (1 + SNR 1 + INR 1 ) Hence, the regionC(1, 1) is within at most log 3 bits of the outer bound region of [1]. From the results of this section, we also know that our scheme achieves the regionC(1, 1) − δ 1 . Evaluating δ 1 for p 1 = p 2 = 1, we see that the proposed scheme achieves within 3 + 3 log 3 ≈ 7.75 bits of the Suh-Tse outer bound region.

APPENDIX G PROOFS OF COROLLARIES 3.1 AND 3.3
In this section, we prove that when the feedback probabilities are sufficiently high, perfect feedback sum-capacity can be achieved (approximately for Gaussian case, exactly for linear deterministic case). The precise statements for the two models are given in Corollaries 3.1 and 3.3.
A. Proof of Corollary 3.1 We will show that when feedback is perfect, the bounds on the sum rate that involve the feedback probabilities become strictly redundant. That is, setting p 1 = p 2 = p, we will prove that the bounds (8), (5) + (6), (5)+(10) 2 , (6)+(9) 2 , and (9)+(10) 3 are all strictly larger than the perfect feedback bound (7) when p = 1 and n 12 , n 21 > 0. Then the result follows by noting that all such bounds are continuous and monotonically increasing functions of p, and hence there must exist a p * < 1 such that whenever p = p * , perfect feedback sum-rate bound (7) is exactly matched by these bounds.
We first prove a claim that will be used in the main proof.

B. Proof of Corollary 3.3
Similar to the proof of Corollary 3.1, we will show that when feedback is perfect, the bounds on the sum rate that involve the feedback probabilities become redundant for the setC(p 1 , p 2 ). Since the capacity region is within a constant gap of the regionC(p 1 , p 2 ), for all channel parameters, the result will follow.
We first prove a claim that will be useful in the proof of the corollary.