Nazim Fatès
email: nazim.fates@loria.fr

A note on the fast convergence of asynchronous Elementary Cellular Automata

Keywords: 0, 2, 8, 10

We tackle the problem of the classification of elementary cellular automata when the cells are updated in with a fully asynchronous scheme (one cell is selected at random at each time step). We establish a proof of convergence in logarithmic time as a function of the size of the automaton. Techniques involve a direct Markov chain analysis or the construction of potential function whose convergence rate is bounded by a particular martingale.

Introduction

This note is a contribution to the study of the 256 Elementary Cellular Automata (ECA) submitted to an asynchronous updating scheme. We are interested in the fully asynchronous case, that is, when only one cell is updated at each time step, chosen uniformly at random in the set of cells. More precisely, we wish to determine which are the rules whose convergence time to a fixed point is very rapid : this time scales logarithmically with the size of the automaton.

Asynchronous cellular automata are currently receiving an increasing attention. Their study concerns various fields such as computability [START_REF] Worsch | intrinsically?) universal asynchronous CA[END_REF], dynamical systems [START_REF] Dennunzio | Computing issues of asynchronous CA[END_REF], or modelling [START_REF] Grilo | Effects of asynchronism on evolutionary games[END_REF] (see Ref. [START_REF] Fatès | A guided tour of asynchronous cellular automata[END_REF] for a survey). The question of the classification of asynchronous cellular automata is still open. One proposition to classify the rules analytically is to study the average time needed to reach a fixed point. Indeed, the way the time of convergence varies as function of the size of the automaton is strongly related to the dynamical behaviour of the system; it can be classified into well-separated "families" [4].

The problem of estimating the convergence rate of asynchronous rules has recently been tackled with an experimental approach [START_REF] Sethi | Experimental study on convergence time of elementary cellular automata under asynchronous update[END_REF][START_REF] Fatès | A note on the classification of the most simple asynchronous cellular automata[END_REF]. On the analytical side, a previous analysis of a subset of the ECA with two quiescent states allowed us to identify (only) two ECA with a logarithmic convergence [4]. But what about the other rules? Can the analysis for this specific two rules be transposed to a wider class of cellular automata ? We here propose to process in three steps and gradually generalise our approach of the fast convergence phenomenon, using Markov-chain analysis and martingale arguments.

Definitions and candidates 2.1 Definitions

An Elementary Cellular Automaton (ECA) is defined as a one-dimensional binary CA with nearest-neighbour interactions. We here tackle the finite case where cells are arranged in a ring and we denote by L = Z/nZ the set of cells. A configuration corresponds to an assignment of a state to each cell, the state of configurations is thus E n = {0, 1} L . The evolution of the ECA is governed by its local function f : {0, 1} 3 → {0, 1}, which specifies how each cell updates its state according to its own state and the states of its two nearest neighbours.

The updating of the automaton is stochastic, we denote by (U t ) t∈N the sequence of independent and identically distributed random variables which uniformly choose select one cell in L. Given a sequence of updates (U t ) and an initial condition x, we can describe the evolution of a fully asynchronous CA by the stochastic process denoted by (x t ) t∈N and defined recursively with:

x 0 = x and x t+1 = F (x, U t ), where ∀i ∈ L, x t+1 i = f (x t i-1 , x t i , x t i+1 ) if i = U t x t i otherwise (1)
For the sake of brevity, the i.i.d. sequence of random updates (U t ) is always implicit and we simply write F (x) as the random variable that describes the configuration obtained by a uniform random update on x. A configuration x ∈ L is called a fixed point if we have F (x) = x with probability 1 (all cells are in a stable state). Note that the synchronous and asynchronous updating induce the same set of fixed points, that is here denoted by FP.

Starting from a configuration x, the convergence time T (x) is the average time required to reach a fixed point. Formally, T (x) = E{min t ∈ N, x t ∈ FP}. For a fixed ring size n, taking some freedom with notations, we define the worst expect convergence as

T (n) = max x∈En T (x).
The 256 ECA will be identified with two different notations. The first one is the classical decimal notation introduced by Wolfram. The second one, called the t-code, consists in assigning to an ECA the letters that designate each active transition of the rule. (A transition is an association of a triplet (x, y, z) to f (x, y, z). We say that a transition is active if its application changes the state of a cell, that is, f (x, y, z) = y). The labels associated to each transition are presented in the following table :  (x,y,z) 000 001 100 101 010 011 110 111

t-code A B C D E F G H .
As an illustration, take the majority rule. It has only two active transitions, (1, 0, 1) → 1 and (0, 1, 0) → 0. Its t-code is thus DE and we will denote by 232 -DE this rule when we want to indicate both codes. For the sake of simplicity, instead of studying the 256 ECA rules, we will restrict our examination to the 88 so-called minimal representative rules. They are the rules which have the smallest decimal code when applying the symmetries of reflexion (left-right exchange) and conjugation (0-1 exchange) and when combining both operations.

Candidates

Among the 88 minimal rules, we previously identified a subset of rules which appear to converge rapidly to a fixed point [START_REF] Fatès | A note on the classification of the most simple asynchronous cellular automata[END_REF]. We divide this set into two classes: the RCH and RCN class group the rules rapid convergence to a homogeneous or non-homogeneous fixed point, respectively. In the RCH class, we find the These diagrams should be interpreted as follows. Time goes from bottom to top; square in blue and white represent cells with states 0 and 1, respectively. The time is rescaled by a factor 1/n: the transition from one line to the other is obtained after n updates. (This explains some discontinuities in the groups of cells). The ring size is fixed to n = 50 and the random evolution is represented over 30 time steps. Recall that the space is a ring, which explains that some sets of coloured cells seem to "appear". It should also be noted that the initial configuration is made of half of the cells contiguously set to 1 and 0. This choice was made on purpose in order to make explicit the fragmentation process at play with these rules.

Classification

"Monotonous" rules

As simple starting point, we consider 76-H, the coupon collector argument still applies as: a) cells in state h are active and b) any h that is updated is turned into a d and c) no h can be created by updating a h. To which set of rules can we generalise this argument? It is important to remark that if we consider T-configurations, updating a cell i can be considered as re-writing operation that will potentially change the labels of three: the updated cell, but also its left and right cells.

In order to find out all the transformations than can occur when a cell is updated, we thus need to consider all the possible triplets, that is the 32 possible sequences of five cells. These transitions are represented on Table 1. In the sequel we call this table the rewriting table. We define a transition of the table to be active if the column to which it belongs corresponds to an active transition. For instance, if we take the majority rule 232 -DE, only the 8 transitions of columns D and E will be active. Definition 1. A strictly monotonous rule is a rule for which each time an active cell is updated, the number of active cells decreases. Proof. Clearly, a rule is strictly monotonous if and only if all the active transitions of the rewriting table lead to a negative difference in the number of active cells. (That is, for each entry of the table the number of active cells before updating is strictly higher than the number of active cells after updating.) For a given rule, let us assign a value 1 or 0 to the eight variables ω a . . . , ω h , depending on whether the T-code of the rule considered contains or does not contain the transitions A, . . . , H, respectively. For instance, for the rule FGH, we have ω a = 0 . . . ω e = 0 and ω f = 1, ω g = 1, ω h = 1.

We can now discuss the possible cases where a decrease in the number of active cells occurs each time an active cell is updated. We denote by ∆(ij) the variation of the number active cells which corresponds to the column i and line j of the rewriting table.

• First case: we assume that H is active, that is, ω h = 1. Looking at the entry (D4) of the rewriting table, we see that transition D can not be active:

ω d = 0. By looking at (B2) we have ∆(B2) = ω h -ω a = 1 -ω a .
As this quantity can not be made negative, we have that B is inactive: ω b = 0. By symmetry, looking at (C3) gives ω c = 0. We now discuss the value of ω a .

-If ω a = 1, then looking at (E1), (F2), (G3), lead to ω e = 0, ω f = 0 and ω g = 0, respectively. As the values of the eight transitions are fixed, we thus find rule AH . (We use a box to denote the minimal representative rules.)

-If ω a = 0, from (H1) we deduce ω e = 1 =⇒ ω f = 1 and ω g = 1. One solution is thus EFGH . The case ω e = 0 gives: FGH ,FH, GH , H . (It can be checked these are all valid solutions.)

• Second case: we assume that H is inactive, that is, ω h = 0. By (F2) and (G3), we obtain: ω f = 0 and ω g = 0. We now discuss on the value of ω e .

-If ω e = 1, entries (E1), (B2) and (C2) give: ω a = 0, ω b = 0 and ω c = 0, respectively. We thus obtain rules E and DE .

-If ω e = 0, it can be observed that the possible candidates are all rules whose active transitions are A, B, C and D. These rules can be reduced to previously examined cases by the 0/1-exchange symmetry, as the active transitions of the symmetric rules will contain only E, F, G and H.

Theorem 2. Strictly monotonous rule have a logarithmic convergence time.

The convergence of rule D and DE has already been studied in a previous work [4]. To upper-bound the convergence convergence time, we simply use the fact that the probability to decrease the number of active cells by at least one is exactly 1/n times the number of active cells. For the lower bound, remark that if a rule differs from identity, that is, if it has at least one active transition, we can take a sequence p ∈ {0, 1} k of k cell states such that p contains an active transition. The configuration x obtained by repeating i times p has a length n = ip and contains at least i active transitions. The system converges if (at least) the i unstable cells are updated, the average time of convergence thus scales as n log i (see coupon collector processes), that is, as n log n. (In the following we call "logarithmic" this type of convergence as we implicitly rescale the time by a factor n for a fair comparison with the synchronous case).

Rules with a monotonous potential

The question is now to determine if the previous argument can be generalised to other rules. As an illustration, let us turn our attention to the rule EH. By examining the rewriting table, it can be seen that this rule is "almost" strictly monotonous, but if we look at the entry (H1), we see that one h can produce two e. The problem produced by this increase in the number of active cells can be solved with the convention that an h counts as much as three e. In this case, a transition of type (H1) would still continue to decrease the number of "weighted" active cells.

However, a difficulty appears at this point as, even with this "weighted" active cells, it is no longer possible to reconduct the previous argument as we have now lost the proportionality that existed between the "activity" and the probability to decrease. We are thus unable to "compare" conveniently the two processes.

Recall that the set of fixed points is denoted by FP. We can now state our specific lemma to establish a logarithmic convergence time.

Lemma 1 (Logarithmic convergence). For a rule R, if there exists an integer k, a potential function W : E n → {0, . . . , k} and a constant α > 0 such that ∀x ∈ E n : W (x) = 0 =⇒ x ∈ FP, (C1)

and ∀x ∈ E n , F (x) = x =⇒ ∆W (x) < 0 (C2) and E{∆W (x)} ≤ -αW (x), ( C3
)
where ∆W (x) = W (F (x)) -W (x), then the worst expected convergence time of R is bounded by log k/α.

In words, if there exists a non-negative potential function W that cancels only on fixed points, and such that, each time a configuration x is updated on an unstable cell, the decrease of W is (at least) proportional to W , then the convergence time is at most logarithmic in the size of the configurations.

Proof. We prove the lemma by recurrence. We define (E i ) as the partition of E n that is induced by W , that is:

E i = {x ∈ E n , W (x) = i}.
Let x be an arbitrary configuration ; we denote by k its potential and by T x its average convergence time. Let T i be the maximum average convergence time for a configuration that has a potential i: T i = max x∈Ei T x . As E 0 is the set of fixed points, we obviously have T 0 = 0.

First, let us introduce the following recurrence relation: T x = 1+ y∈En p x,y T y , where p x,y denotes the probability to go from state x to state y. This relation, often called the step-forward equation, is a "classical" tool from Markov chain theory.

For i ∈ {0, . . . , k -1}, let λ i = y∈Ei p x,y be the probability to go from x to a configuration of potential i (recall that the potential can only decrease). Grouping all the states of equal potential, the step-forward equation gives:

T x ≤ 1 + p x,x T x + k-1 i=0 λ i T i .
(

) 2
We define δ = 1 -p x,x = k-1 i=0 λ i , this quantity represents the probability to "leave" state x after one (random) update. The previous equation becomes:

T x = 1 δ 1 + k-1 i=0 λ i T i . (3)
In order to prove the theorem by recurrence, let P k be the following property:

T k ≤ 1 α H k where H k = 1 k + 1 k -1 + • • • + 1 1 . (4)
We now prove that P k holds for every k.

First, let us show that P 1 holds. Let us take x ∈ E 1 . Condition C2 of the Lemma implies that: Pr[W (F (x)) = 0] ≥ α, that is, Pr[F (x) ∈ FP] ≥ α, from which we directly derive T 1 ≤ 1/α. Now, we assume P 1 , . . . , P k-1 and prove P k . The idea is to compare the value of T k with 1 α H i . To this end, we study the sign of ∆ = δαT k -δH i : showing that P k is valid is equivalent to showing that ∆ is negative. (The form of ∆ is chosen in order to avoid manipulating fractions as as much as possible).

We have:

∆ = α + k-1 i=0 λ i αT i -δ • H k (5)
which, using the hypothesis P k-1 , gives:

∆ ≤ α + k-1 i=0 λ i H i -δ • H k ≤ α + k-1 i=0 λ i (H i -H k ) (6)
given that

δ = λ 0 +• • •+λ k . Finally, by noting that ∀i ∈ {1, . . . , k}, H i -H k ≥ i k , we obtain: k∆ ≤ kα - k-1 i=0 (k -i)λ i ,
which shows that ∆ is negative by using the conditions of the decrease in potential. ∆ is thus negative for all possible configurations of potential k, which proves P k . We thus have T k ≤ H k /α ≤ log k/α, which concludes the proof.

We can now apply this lemma to extend the list of monotonous rules. Definition 2. We say that a potential function W : E n → N is balanced if the difference of potential brought by the update of a cell i is only a function of the T-label of cell i. W is said to be p-linear if it is defined as a positive linear combination of the number of cells of a given configuration, that is,

W (x) = ω a a(x) + • • • + ω h h(x)
with ω a , . . . , ω h ∈ N. W is i-linear (short of instabilitylinear) if the positive coefficients all correspond to active transitions.

Claim 1. W is balanced if and only if: ω a +ω d = ω b +ω c and ω e +ω h = ω f +ω g .

We have no intuitive explanation of this fact, which was discovered empirically. It can be checked that if the two conditions are verified, the entries of each line of the transition table are equal, which guarantees that the rule is balanced.

Theorem 3. Among the RCN and RCH class, rules 5-AFGH, 8-EGH, 13-AGH, 72-EH are the only (non-strictly) monotonous rules ; their convergence time is logarithmic.

Proof. To show this, we examine which are the "candidates" to be monotonous. First, it can be remarked that if the T-code of a rule contains two letters in that form one of these couples: A-E, B-F, C-G or D-H, then the rule is not strictly monotonous. Indeed if a rules has two of such "opposed" active transitions, a configuration which is updated twice on a cell with such a transition comes back to initial state, which is contradiction with the hypothesis of monotony. Second, if we also rule out from the empirically-made list of candidates (RCH + RCN) the strictly monotonous rules, the only candidates left are: EH, EGH, BEGH, AFGH, and AGH.

We can also rule out BEGH with a specific example. If we start from configuration 0110, and update the third cell, we obtain the configuration 0100. If we then the first cell, we come back to the initial state 0110, which is also a contradiction with the monotony of the rule.

We now exhibit relevant potential functions for the four rules that remain. For a particular configuration x ∈ E n , we denote by a(x), . . . , h(x) the number of occurrences of the t-labels a, . . . , h in x. The potential functions W (x) will be constructed as linear combinations of these functions and the argument x will be omitted for brevity. Note that, for a given potential function, being balanced is equivalent to having the same values of decrease in potential for a particular column of the rewriting table: the decrease of potential of a cell having a given t-label t is denoted by δ t .

Case of EGH. We take W = e + 2g + h. This potential verifies C1 as it is p-linear. It verifies C2 as it is balanced with:

δ E = δ G = δ H = -1. It also directly verifies C3 because it is i-linear.
Case of AFGH. Similarly, we take W = a + f + g + 2h = e + 2g + h. This potential verifies C1 as it is i-linear. It can also be checked that the potential decreases by at least 1, when an A a For a G is updated and that the potential decreases by 4 when an H is updated. Condition C2 is thus verified and we have:

n.E{∆W } ≤ -a -f -g -4h (7) ≤ -a -f -g -2h ≤ -W (8)
Condition C3 is thus verified with ǫ = 1/n. (Due to lack of space, rest of the proof is put in annex, see Sec. 4.1.)

Rules with an average decrease of potential

Our efforts to generalise the first argument allowed us to deal with "only" four more rules. The reason why this attempt had a limited success is not so difficult to guess: by requiring that the potential always decreases when an active cell was updated, we were demanding too much. We now present a lemma that allows us to extend one step further the domain of application of the mathematical analysis: in this new step, we will only require that the decrease happens on average. However, in order to get a logarithmic convergence time, we need to impose that the decrease of the potential is proportional to the the current value of the potential. Lemma 2. Let (X t ) t∈N be a stochastic process whose values are in {0, . . . , k} and (F t ) t∈N a filtration adapted to it. If there exists a constant 0 < ǫ < 1 such that ∀t ∈ N: E{X t+1 -X t | F t } ≤ -ǫX t then the average time for reaching 0 is upper-bounded by -log k+1 log 1-ǫ .

Proof. First let us, introduce the stochastic process defined by: Y t = (X t + 1)λ t . Our goal is to show that for a proper setting of λ, (Y t ) is a supermartingale and to use this to bound the time needed for (X t ) to hit zero. We have:

E{ Y t+1 Y t | F t } = E{ X t+1 + 1 X t + 1 λ | F t } = λ • E{ Xt+1 Xt + 1 Xt 1 + 1 Xt | F t } (9) ≤ λ • E{ X t+1 X t | F t } (10)
We rewrite the condition on the average decrease of X t as:

E{ Xt+1 Xt | F t } ≤ 1 -ǫ, from which we deduce that λ = 1/(1 -ǫ) implies that (Y t ) is a supermartingale (that is, E{Y t+1 -Y t | F t } ≤ 0).
Let T be the random variable defined as T = min t∈N X t = 0. This defines an stopping time and, according to Doob's optional stopping time theorem, one can define the random variable Y T and write that: E{Y T } ≤ E{Y 0 }, which gives E{Y T } ≤ k + 1. On the other hand we have: E{Y T } = E{λ T } with λ ≥ 1. Using the fact that x → λ x is a concave function, we can apply Jensen's inequality and write:

λ E{T } ≤ E{λ T } ≤ k + 1,
Case of AGH. We take W = a + 2g + 2h. This potential verifies C1 as it is p-linear. It is not balanced, however, it can be checked by looking at each entry individually that: the potential decreases by at least 1, when an A or a G is updated (entries C4,G1 and G3), the potential decreases by 4 when an H is updated. Condition C2 is thus verified. We also we have: W is also a suitable function for BDEFGH. We have the same decrease for each transition as before, to which we add δ B = 2. We thus write:

Theorem 1 .

 1 The (minimal) rules that are strictly monotonous are: 0-EFGH, 4-FGH, 12-GH, 76-H, 77-AH, 200-E, 232-DE.

  Condition C3 is verified with ǫ = 1/2n.

4. 2 1 - 3 - 2 - 2 - 1 .

 213221 Proof of the existence of a suitable potential function for DEFGH, BDEFGH, and DEGHFor DEFGH, we proceed by taking again W = 3e+5f +2h. This balanced potential rules generates the following changes in potential:tr. D E F G H δAs for the previous case, we write:2nE{∆W (x)|x} = 2d -6e -4f -4g -2h ≤ 2e + 2f -6e -8f -2h as: d ≤ e + f and f = g ≤ -4e -6f -2h ≤ -3e -5f -2h ≤ W (x)

  2nE{∆W (x)|x} = 2b + 2d -6e -4f -4g -2h = -4e -6f -2h as: b + d = e + f and f = g ≤ -3e -5f -2h ≤ W (x)Last, W is also a suitable function for DEGH. Indeed, the decreases of potential are: tr. D E G H δ 1 -3 -2 -1 and we have:nE{∆W (x)|x} = d -3e -2g -h ≤ e + f -3e -2f -h as: d ≤ e + f and f = g ≤ -2e -f -hWe thus have 5nE{∆W (x)|x} ≤ -10e -5f -5h ≤ -3e -5f -2h ≤ W (x).

Table 1 :

 1 Table of the 32 possible re-writing triplets of T-codes. The column corresponds to the 8 possible states of the central cell and the lines corresponds to the 4 possible states of the left and right cells.

		A	B	C	D	E	F	G	H
	1	aaa bec	abe bfg	eca fgc	ede fhg	bec aaa	bfg abe	fgc eca	fhg ede
	2	aab bed	abf bfh	ecb fgd	edf fhh	bed aab	bfh abf	fgd ecb	fhh edf
	3	caa dec	cbe dfg	gca hgc	gde hhg	dec caa	dfg cbe	hgc gca	hhg gde
	4	cab ded	cbf dfh	gcb hgd	gdf hhh	ded cab	dfh cbf	hgd gcb	hhh gdf

from which we deduce: E{T } ≤ ln(k+1) ln λ and the fact that the mean value of T is bounded by Θ(ln k).

We now apply the lemma to four rules. Before we can go to the proof we use the following fact: Claim 2. If for a rule R, there exists a positive integer m, a p-linear function W such that for every ring size n ∈ N:

then the rule has a logarithmic convergence.

This fact simply represents an application of Lemma 2 in our context. It is obtained by taking ǫ = 1/m.n and -ln(1 -ǫ) ∼ ǫ for ǫ → 0.

Proof. We begin with rule BEFGH. We take as a potential function: W = 3e + 5f + 2h. (The form of W can be justified by the necessary condition: ω a + ω h < ω d + ω e < 2ω h obtained by looking at the variation of potential of the two confgurations: all-1 and 010.) W is balanced and the variation of potential associated to each transition is:

≤ 6e + 6f -9e -12f -3h as: b ≤ e + f and f = g (13)

The proofs for rules DEFGH, BDEFGH and DEGH are omitted due to lack of space. (See Annex, sec. 4.2)

A non-logarithmic rule

Contrarily to what was first thought, Rule 74-BEH does not have logarithmic convergence. This can be observed if we observe what happens to the fixed point (011) k (with k large enough) and change one cell state: a "cascade" propagates from right to left and makes the system progressively converge to 0. (The construction can be made for all ring sizes: repeat pattern 001 and then "complete" with something). This error of classification underlines the need to distinguish the average case and the worst case.


Martina Cardone
email: cardone@eurecom.fr

Daniela Tuninetti
email: danielat@uic.edu

Raymond Knopp
email: knopp@eurecom.fr

Umer Salim
email: umer.salim@intel.com

On the Gaussian Interference Channel with Half-Duplex Causal Cognition

Keywords: causal unilateral cooperation, half-duplex, generalized degrees of freedom, inner bound, outer bound, constant gap

This paper studies the two-user Gaussian interference channel with half-duplex causal cognition. This channel model consists of two source-destination pairs sharing a common wireless channel. One of the sources, referred to as the cognitive, overhears the other source, referred to as the primary, through a noisy link and can therefore assist in sending the primary's data. Due to practical constraints, the cognitive source is assumed to work in half-duplex mode, that is, it cannot simultaneously transmit and receive. This model is more relevant for practical cognitive radio systems than the classical information theoretic cognitive channel model, where the cognitive source is assumed to have a non-causal knowledge of the primary's message. Different network topologies are considered, corresponding to different interference scenarios: (i) the interference-symmetric scenario, where both destinations are in the coverage area of the two sources and hence experience interference, and (ii) the interference-asymmetric scenario, where one destination does not suffer from interference. For each topology the sum-rate performance is studied by first deriving the generalized Degrees of Freedom (gDoF), or "sum-capacity pre-log" in the high-SNR regime, and then showing relatively simple coding schemes that achieve a sum-rate upper bound to within a constant number of bits for any SNR. Finally, the gDoF of the channel is compared to that of the non-cooperative interference channel and to that of the non-causal cognitive channel to identify the parameter regimes where half-duplex causal cognition is useless in practice or attains its ideal ultimate limit, respectively. Index Terms-Cognitive radio

I. INTRODUCTION

The next major upgrade of fourth generation cellular networks will consist of a massive deployment of radio infrastructure nodes (i.e., base stations and relay stations) enabling different aspects of the cognitive radio paradigm in an operated network scenario [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF]. Cognitive radio concepts, such as centralized and distributed interference management and collaboration between radio nodes, will allow flexible and multi-band access to the spectrum. Radio infrastructure nodes will come in several flavors, characterized primarily by their available bandwidth and number of concurrent frequency channels on which they can simultaneously operate (spectrum aggregation), the capacity of their backhaul links to the operator's core network (wireless, high throughput/low-latency

The results in this paper were presented in part to the 2013 IEEE International Symposium on Information Theory [START_REF] Cardone | The symmetric sum-capacity of the gaussian half-duplex causal cognitive interference channel to within a constant gap[END_REF].

Manuscript received date: April 1, 2013 Manuscript revised dates: August 20, 2013 and October 30, 2013 wired interconnect, non carrier-grade wired backhaul, etc.), their ability to collaborate with other similar nodes, and their coverage area and tolerance to interference. The combined use of several infrastructure nodes with different features will result in so-called heterogenous networks. The collaborative features of heterogeneous networks can range from fullycentralized Multiple-Input-Multiple-Output (MIMO) with distributed antennas (very high-quality backhaul links for node connection) achieving full use of the network resources, to distributed (causal) MIMO with improved resource utilization compared to point-to-point channels, or to looser forms of collaboration such as joint time/frequency-allocation for improving link-quality.

In this paper we consider a particular aspect of future heterogeneous networks, namely, a practical application of the cognitive overlay paradigm [START_REF] Goldsmith | Breaking spectrum gridlock with cognitive radios: An information theoretic perspective[END_REF]. The channel is modeled as a Gaussian two-user Half-Duplex Causal Cognitive Interference Channel (G-HD-CCIC) where one cognitive source, CTx, overhears the other primary source, PTx, through a noisy channel. The CTx assists in sending the PTx's data to the primary destination, PRx. In the language of [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF], the PTx could be a macro-base station with a large coverage area and the CTx a small-cell base station or relay station (indoor or a localized coverage-area). The PTx aims to serve a largenumber of users, here for simplicity modeled by a single PRx, which may or may not be in the coverage area of CTx. The CTx aims to serve a smaller-number of users, here modeled for simplicity as a single CRx, which may or may not be in the coverage area of PTx. The link between the two sources is noisy and of limited capacity. We assume that both sources have independently generated messages, each known at the corresponding source only. This corresponds to a scenario where PTx and CTx have separate interconnections to the core network or where the schedulers in PTx and CTx operate in a non-coordinated fashion. We further consider the case where the link from PTx to CTx is unilateral so that CTx can causally learn the PTx's message but not vice-versa. This models the scenario where the coverage-area of CTx is smaller than that of PTx. The final modeling assumption is that CTx operates in half-duplex mode, meaning that in any time/frequency slot the CTx cannot simultaneously transmit and receive.

We study different deployment configurations, which correspond to different interference scenarios. In the interferencesymmetric scenario (see Fig. 1, left) both destinations are in the coverage area of the two sources; this implies that both destinations are interfered. In the interference-asymmetric scenario, one destination does not suffer from interference; in this case one of the interfering links is set to zero. Due to the asymmetry in the cooperation, two interference-asymmetric scenarios must be considered: the Z-channel, where the link from PTx to CRx is non-existent (i.e., CRx is out of the range of PTx, see Fig. 1, middle) and the S-channel, where the link from CTx to PRx is non-existent (i.e., PRx is out of the range of CTx, see Fig. 1, right). For each topology we study the ultimate sum-rate performance in the spirit of [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF]. We first derive, in closed form, the generalized Degrees-of-Freedom (gDoF), or "sum-capacity pre-log" in the high-SNR regime, and we then show relatively simple coding schemes that achieve the sum-rate upper bound to within a constant number of bits regardless of the SNR.

A. Related Work

Non-causal CIC: In the classical information theoretic cognitive radio overlay paradigm [START_REF] Goldsmith | Breaking spectrum gridlock with cognitive radios: An information theoretic perspective[END_REF], the CTx is assumed to have non-causal, i.e., before transmission begins, knowledge of the message and codebook of the PTx [START_REF] Devroye | Achievable rates in cognitive radio channels[END_REF]. The capacity region of this system in Gaussian noise is known exactly for some channel parameters and to within 1 bit otherwise [START_REF] Rini | Inner and outer bounds for the gaussian cognitive interference channel and new capacity results[END_REF].

The assumption of a priori knowledge at the CTx is too idealistic for practical schemes and reasonable only in certain situations, such as when the PTx and the CTx are close to each other. Motivated by this practical issue, we assume the existence of a noisy link between the two sources through which the CTx can causally learn the PTx's message. This model is an IC with source cooperation, more specifically, and IC with unilateral cooperation. As such, the CCIC can be studied within the framework of the IC with source cooperation.

Full-Duplex IC with bilateral source cooperation: The cooperative IC was first studied in [START_REF] Host-Madsen | Capacity bounds for cooperative diversity[END_REF], where Full-Duplex (FD) bilateral source or destination cooperation was analyzed by developing capacity outer and inner bounds for the Gaussian noise channel. In [START_REF] Tuninetti | An outer bound region for interference channels with generalized feedback[END_REF] and [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF], outer bound regions were derived for the case of general source cooperation. In [START_REF] Yang | Interference channel with generalized feedback (a.k.a. with source cooperation): Part i: Achievable region[END_REF], an achiev-able scheme for the IC with FD bilateral source cooperation was proposed by using rate-splitting [START_REF] Han | A new achievable rate region for the interference channel[END_REF] and Dirty-Paper-Coding (DPC) [START_REF] Costa | Writing on dirty paper (corresp.)[END_REF]. For FD bilateral source cooperation, [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF] characterized the Gaussian sum-capacity to within 20 bits for all channel parameters by assuming symmetric, i.e., same strength, cooperation links, while [START_REF] Yang | Interference channels with source cooperation in the strong cooperation regime: Symmetric capacity to within 2 bits/s/hz with dirty paper coding[END_REF] to within 4 bits in the case of "strong cooperation" with symmetric cooperation, direct and interfering links.

Full-Duplex IC with unilateral source cooperation: FD unilateral source cooperation is a special case of FD bilateral source cooperation in which only one of the sources cooperates. This model was studied in [START_REF] Mirmohseni | On the capacity of interference channel with causal and noncausal generalized feedback at the cognitive transmitter[END_REF] for the case of "look ahead" at the cognitive source, meaning that at a given time instant CTx has non-causal access to L ≥ 0 future channel outputs. The authors of [START_REF] Mirmohseni | On the capacity of interference channel with causal and noncausal generalized feedback at the cognitive transmitter[END_REF] derived potentially tighter outer bounds for the FD-CCIC channel (i.e., case L = 0) than those of [START_REF] Tuninetti | An outer bound region for interference channels with generalized feedback[END_REF] specialized to unilateral cooperation; unfortunately it is not clear how to evaluate these bounds in Gaussian noise because they are expressed as a function of auxiliary random variables jointly distributed with the inputs. The achievable region in [14, Theorem 5 / Corollary 1] is also no smaller than that of [START_REF] Yang | Interference channel with generalized feedback (a.k.a. with source cooperation): Part i: Achievable region[END_REF] specialized to the case of unilateral cooperation (see [START_REF] Mirmohseni | On the capacity of interference channel with causal and noncausal generalized feedback at the cognitive transmitter[END_REF]Remark 2,point 6]); unfortunately its evaluation in general is very involved as the rate region is specified by 9 jointly distributed auxiliary random variables and by 30 rate constraints. In [START_REF] Mirmohseni | On the capacity of interference channel with causal and noncausal generalized feedback at the cognitive transmitter[END_REF] inner bounds were evaluated numerically, but a performance guarantee in terms of (sum-)capacity to within a constant gap was not given.

In [START_REF] Cardone | On the interference channel with causal cognition[END_REF], the capacity region of the IC with FD source cooperation was characterized to within 2 bits for a large set of channel parameters that, roughly speaking, excludes the case of weak interference at both receivers. Although the FD-CCIC represents a more realistic model for practical cognitive radio systems than the non-causal CIC, the FD assumption at the CTx has practical restrictions such as the inability to perfectly cancel the self-interference. Due to this practical constraint, in this work we assume that the CTx operates in HD mode.

Half-Duplex IC with source cooperation: HD cooperation can be studied as a special case of FD cooperation by using the formalism of [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF]. This approach is usually not followed in the literature, often making imprecise claims about capacity and Gaussian capacity to within a constant gap. In [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF], it was shown that in the relay channel a larger rate can be achieved by randomly switching between the transmit-and receive-phases at the HD relay. In this way, the randomness that lies into the switch can be harnessed to transmit (at most 1 bit per channel use of) additional information to the destination. We shall refer to this mode of operation as random switch [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF], as opposed to deterministic switch where the transmit-and receive-phases are predetermined and therefore known to all nodes. In [START_REF] Cardone | Gaussian halfduplex relay channels: Generalized degrees of freedom and constant gap result[END_REF] we showed that random switch is necessary to achieve capacity for a class of deterministic HD relay channels.

In [START_REF] Wu | Interference channels with half-duplex source cooperation[END_REF], the sum-capacity of the Gaussian IC with HD source cooperation and deterministic switch was characterized to within 20 bits and 31 bits for the case of symmetric (direct, interference and cooperation links) bilateral and general unilateral cooperation, respectively. These approximately optimal schemes are inspired by the Linear Deterministic Approximation (LDA) of the Gaussian noise channel.

Deterministic / noiseless channel models: The LDA, first proposed in [START_REF] Avestimehr | Wireless network information flow: A deterministic approach[END_REF] in the context of relay networks, captures in a simple deterministic way the interaction between interfering signals of different strengths. In the LDA the effect of the noise is neglected and the signal interaction is modeled as bit-wise additions. Thereby, this simplification allows for a complete characterization of the capacity region in many instances where the capacity of the noisy channel counterpart is a long standing open problem. More importantly, the capacity achieving schemes for the LDA model can be 'translated' into schemes for the Gaussian noise case that, although not optimal in general, are at most a constant and finite number of bits away from an outer bound regardless of the channel parameters. For example, in the non-cooperative IC, the evaluation of the Han-Kobayashi region [START_REF] Han | A new achievable rate region for the interference channel[END_REF] in the Gaussian noise case is a formidable task [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF], which does not appear to provide useful insights in its full generality; the LDA model instead reveals the (approximate) optimality of the simple ratesplitting method proposed in [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF], namely that, whatever is treated as noise should be received at the level of the noise [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF]; this strategy does not exactly achieve capacity, but it is optimal to within 1 bit. The "it is better to approximate"-philosophy [START_REF] Tse | It's easier to approximate[END_REF] behind the LDA model has enabled great progress in longstanding open problems, including the non-cooperative IC [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF] and the relay channel [START_REF] Avestimehr | Wireless network information flow: A deterministic approach[END_REF].

B. Contributions

This work characterizes both the interference-symmetric and interference-asymmetric sum-capacity to within a constant gap, hence the gDoF, of the G-HD-CCIC. Our main contributions can be summarized as follows:

• We overcome a number of limitations and improve on the results of [START_REF] Wu | Interference channels with half-duplex source cooperation[END_REF] as follows: (i) we properly account for random switch at the CTx in the outer bound by using the framework of [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF], i.e., without the need to develop a separate theory for the HD case as in [START_REF] Wu | Interference channels with half-duplex source cooperation[END_REF], (ii) we consider the classical definition of sum-capacity without introducing any "back-off" in the PTx rate, which can be interpreted as a sort of interference margin at the PRx, (iii) we derive the gDoF in closed form rather than expressing it implicitly as the solution of a linear program, and (iv) we reduce the gap to 8.5048 bits for the interferencesymmetric case, and to 4.507 bits and 5 bits for the Zand S-channels, respectively, through novel achievable schemes.

• As in [START_REF] Wu | Interference channels with half-duplex source cooperation[END_REF], our 'optimal to within a constant gap' schemes for the G-HD-CCIC are inspired by the LDA model. Using the LDA model, we obtain a closed-form expression for the different optimization variables (e.g., schedule, power splits, coding schemes and corresponding decoding orders, etc.). This result sheds light on how the design of the HD CTx should be properly carried out, which is an important practical task for future wireless networks.

• We compare the gDoF of the G-HD-CCIC with that of: (i) the classical non-cooperative IC, i.e., where there is no cooperation among the nodes [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF], and (ii) the non-causal cognitive IC, i.e., where the CTx has a non-causal knowledge of the PTx's message [START_REF] Rini | Inner and outer bounds for the gaussian cognitive interference channel and new capacity results[END_REF]. In particular, we find the parameter regimes where HD unilateral cooperation does not yield benefits compared to the non-cooperative IC [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF], and those where it attains the ultimate performance limits of the non-causal CIC [START_REF] Rini | Inner and outer bounds for the gaussian cognitive interference channel and new capacity results[END_REF]. Interestingly, we show that in regimes where the G-HD-CCIC outperforms the non-cooperative IC the cooperation link must be able to reliably convey a rate larger than the sumcapacity of the corresponding non-cooperative IC. Moreover, we identify the regimes where a loss incurs by using HD mode of operation at the CTx with respect to FD [START_REF] Cardone | On the interference channel with causal cognition[END_REF].

C. Paper Organization

The rest of the paper is organized as follows. Section II describes the channel model and defines the sum-capacity to within a constant gap and the gDoF. Section III derives an outer bound for our HD model by adapting known FD bounds. Sections IV, V and VI characterize the sum-capacity to within a constant gap, and hence the gDoF, for the interferencesymmetric, the Zand S-channels, respectively. Section VII concludes the paper. The details of the proofs can be found in Appendix.

II. CHANNEL MODEL

We use the notation convention of [START_REF] Gamal | Network Information Theory[END_REF]:

[n 1 : n 2 ] is the set of integers from n 1 to n 2 ≥ n 1 , [x] + := max{0, x} for x ∈ R,
and Y j is a vector of length j with component (Y 1 , . . . , Y j ).

We consider the single-antenna G-HD-CCIC, whose input/output relationship is given by (1) at the top of next page. The channel inputs are subject, without loss of generality, to the average power constraint E |X i | 2 ≤ 1, i ∈ {p, c} (i.e., non-unitary power constraints can be incorporated into the channel gains). M c is the state random variable that indicates whether the CTx is in receive-mode (M c = 0) or in transmitmode (M c = 1) [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF]. A in the channel transfer matrix indicates the channel gain that does not affect the capacity region because of the HD constraint. The channel parameters (C, S p , S c , I p , I c , θ p , θ c ) ∈ R 7 + are fixed and so known to all

  Y f Y p Y c   =   1 -M c 0 0 0 1 0 0 0 1     √ C S p √ I c e jθc I p e jθp √ S c   1 0 0 M c X p X c +   Z f Z p Z c   (1)
nodes. Some of the channel gains can be taken to be realvalued and non-negative since a node can compensate for the phase of one of its channel gains. In the following we assume that the channel sub-matrix

Sp Ic e jθc

Ip e jθp Sc is fullrank (otherwise one channel output is a degraded version of the other and hence one receiver can, without loss of generality, decode all messages). The noises are independent proper-complex Gaussian random variables with, without loss of generality, zero mean and unit variance.

PTx has a message W p ∈ [1 : 2 N Rp ] for PRx and CTx has a message W c ∈ [1 : 2 N Rc ] for CRx, where N denotes the codeword length and R p and R c are the transmission rates for PTx and CTx, respectively, measured in bits per channel use. The messages W p and W c are independent and uniformly distributed on their respective domains. At time t, t ∈ [1 : N ], PTx maps its message W p into a channel input symbol according to X p,t (W p ) and CTx encodes its message W c and its past channel observations into

X c,t W c , Y t-1 f .
The channel is assumed to be memoryless. At time N , PRx outputs an estimate of W p based on all its channel observations as

W p Y N p and similarly CRx outputs W c Y N c . The capacity region is the convex closure of all non-negative rate pairs (R p , R c ) such that max i∈{p,c} P W i = W i → 0 as N → +∞.
The exact capacity of the CCIC is open. We make progress towards understanding the ultimate performance limits of the G-HD-CCIC by approximately characterizing its sum-capacity in the spirit of [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF]. The sum-capacity is known to within GAP bits if one can show a sum-rate inner bound (R p + R c ) (IB) and a sum-rate outer bound

(R p + R c ) (OB) such that (R p + R c ) (OB) -(R p + R c ) (IB) ≤ GAP,
where GAP is a constant with respect to the channel parameters.

The knowledge of the sum-capacity to within a constant gap implies the exact knowledge of the sum-capacity pre-log factor at high SNR [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF]. By following [4, Section V], for some SNR > 0 and for some non-negative (α c , α p , β), we let

S c = S p = S := SNR 1 , C := SNR β I c := SNR αc , I p := SNR αp , (2)
where α i is the ratio of the received power on the interference link i ∈ {p, c} expressed in dB over the received power on the direct link expressed in dB, and where β is defined similarly for the cooperation link. Note that the direct links are assumed here to have the same strength in order to reduce the number of parameters. The gDoF, following [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF], is defined as

d := lim SNR→+∞ max{R p + R c } 2 log(1 + SNR) (3)
where the maximization is intended over all possible achievable rates (R p , R c ). The normalization in (3) of the maximum sum-rate is with respect to the sum-capacity of an interferencefree network. In the non-cooperative case d (NoCoop) ≤ 1 be-cause the absence of interference is the best possible scenario.

In the cooperative case, interference can be beneficial because it can carry useful cooperative information [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF], [START_REF] Yang | Interference channels with source cooperation in the strong cooperation regime: Symmetric capacity to within 2 bits/s/hz with dirty paper coding[END_REF] and, as a result, d in (3) can be larger than 1. In the limiting ideal case, where the CTx non-causally knows the PTx's message, the gDoF, indicated as d (Ideal) , can grow with the interference exponent α. In general, d (NoCoop) ≤ d ≤ d (Ideal) .

In this work we derive results for both the interferencesymmetric and interference-asymmetric cases. In particular, the interference-symmetric channel has α p = α c = α, the Z-channel has α c = α and α p = 0, and the S-channel has α p = α and α c = 0, for some α ≥ 0. For these cases, the gDoF in ( 3) is a function of (α, β); we shall refer to α as the 'interference exponent' and to β as the 'cooperation exponent'. We expect that d (NoCoop) = d(α, 0) and d (Ideal) = lim β→∞ d(α, β).

III. SUM-CAPACITY UPPER BOUND

Here we specialize the known outer bounds for FD bilateral source cooperation in [START_REF] Host-Madsen | Capacity bounds for cooperative diversity[END_REF], [START_REF] Tuninetti | An outer bound region for interference channels with generalized feedback[END_REF], [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF] to the case of HD unilateral cooperation by following the approach of [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF]. We can show that (4), at the top of next page, holds by proceeding through the following steps: (i) in the outer bounds for the general memoryless IC with bilateral FD source cooperation, we substitute X c with the pair (X c , M c ) [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF]; (ii) for any triplet of random variables (A, B, C) we bound

I(A, X c , M c ; B|C) ≤ H(M c ) + I(A, X c ; B|C, M c ) since, for a binary-valued random variable M c , we have I(M c ; B|C) ≤ H(M c ) = H(γ) for some γ := P[M c = 0] ∈ [0, 1] and where H(γ) = -γ log(γ) -(1 - γ) log(1 -γ); (iii)
for all the remaining mutual information terms, which are conditioned on M c = , ∈ [0 : 1], the "Gaussian maximizes entropy"-principle guarantees that in order to exhaust all possible input distributions it suffices to consider jointly Gaussian proper-complex inputs with covariance matrix

P p, ρ P p, P c, ρ * P p, P c, P c,
for |ρ | ≤ 1 and (P p,0 , P p,1 , P c,0 , P c,1 ) ∈ R 4 + satisfying the power constraint γP u,0 + (1γ) P u,1 ≤ 1, u ∈ {p, c}; (iv) since PTx always transmits we define, for some τ ∈ [0, 1], P p,0 = τ γ and P p,1 = 1-τ 1-γ , while, since the CTx transmission only affects the receivers outputs when M c = 1, we let P c,0 = 0 and P c,1 = 1 1-γ ; (v) the sum-rate upper bound in ( 5) is from [7, min{eq.(81)+eq.(82), eq.( 83)}], that in ( 6) is from [8, min{eq.(4d), eq.(4e)}], and that in [START_REF] Host-Madsen | Capacity bounds for cooperative diversity[END_REF] is from [9, eq.( 6)-( 7)] and are obtained by upper bounding each mutual information term over (ρ 0 , ρ 1 , τ ) ∈ [0, 1] 3 , as well as over the phases of the channel gains, while keeping γ as fixed; (vi) each outer bound is also characterized by a linear combination of terms of the type 'γ log (γ)', which can be maximized over γ ∈ [0, 1] thus giving the additive constants in ( 5), ( 6) and [START_REF] Host-Madsen | Capacity bounds for cooperative diversity[END_REF].

(R p + R c ) (OB) := min (R p + R c ) (CS) , (R p + R c ) (DT) , (R p + R c ) (PV) for ( 4
) (R p + R c ) (CS) := 2.507 + min γ log (1 + S + C) + 2 (1 -γ) log (1 + S) , γ log (1 + S + I p ) + + (1 -γ) log 1 + √ S + I c 2 + √ S + I p 2 + S + I p I c 2 (5) (R p + R c ) (DT) := min 3 + γ log (1 + S) + (1 -γ) log max {I c , S} I c • 1 + √ S + I c 2 , 2 + γ log (1 + C + max {I p , S}) + (1 -γ) log max {I p , S} I p • 1 + √ S + I p 2 (6)
(R p + R c ) (PV) := 3.5048 + γ log (1 + S + C + I p ) + (1 -γ) log 1 + I p + S I c + + (1 -γ) log 1 + I c + S I p . (7)

IV. THE INTERFERENCE-SYMMETRIC G-HD-CCIC

When the interfering links have the same strength I c = I p = SNR α , we can show Theorem 1. The sum-capacity upper bound in (4) is achievable to within 8.5048 bits regardless of the actual value of the channel parameters for the interference-symmetric G-HD-CCIC. Therefore, the gDoF can be obtained from (4) and equals

d (SYM) = max γ∈[0,1] 1 2 min γ max {1, β} + 2 (1 -γ) , (8a) γ + (1 -γ) max {1, α} + [1 -α] + , (8b)
γ max {α, β, 1} + 2 (1 -γ) max {α, 1 -α} (8c) =            1 -α + 1 2 [β-2+2α] + α β+α-1 α ∈ [0, 1/2) α + 1 2 [β-2α] + (2-3α) β-3α+1 α ∈ [1/2, 2/3) max 1 -1 2 α, 1 2 α α ∈ [2/3, 2) 1 + 1 2 [β-2] + (α-2) β+α-3 α ∈ [2, ∞) . ( 8d
)
Proof: The details of the proof can be found in Appendix A-A.

The gDoF expression in (8d), to be compared with d (NoCoop) = min{1, max{1α, α}, max{1α/2, α/2}}, and d (Ideal) = max{1α/2, α/2}, has an interesting interpretation, which we shall discuss in details for the different interference regimes in the following. Before we do so, we introduce the LDA model, or deterministic high-SNR approximation of a Gaussian noise channel [START_REF] Avestimehr | Wireless network information flow: A deterministic approach[END_REF], which will help us to develop insights into approximately optimal achievable schemes. The symmetric LDA has input/output relationship

Y f = (1 -M c ) S n-n f X p Y p = S n-n d X p + M c S n-n i X c Y c = S n-n i X p + M c S n-n d X c
where: (n d , n f , n i ) are non-negative integers with n := max{n f , n d , n i }, M c is the binary random variable that indicates the state of CTx, all input and output vectors have length n and take value in GF(2), the sum is understood bitwise on GF(2), and S is the down-shift matrix of dimension n. The model has the following interpretation. The PTx sends a length-n vector X p , whose top n d bits are received at the PRx through the direct link, the top n i bits are received at the CRx through the interference link, and the top n f bits are received at the CTx through the cooperation/feedback link; similarly for X c . The fact that only a certain number of bits are observed at a given node is a consequence of the 'down shift' operation through the matrix S. The bits not observed at a node are said to be 'below the noise floor'. The parameters of the LDA model can be related to those of the G-HD-CCIC in [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF] as

n d = log(1 + S c ) = log(1 + S p ) n i = log(1 + I c ) = log(1 + I p ) n f = log(1 + C) .
In the symmetric case we indicate α := n i /n d and β := n f /n d as they play the same role of the corresponding quantities in [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF]. The simplicity of the LDA model allows for the exact capacity characterization in many instances where the capacity of the Gaussian counterpart is open. Moreover, the sumcapacity of the LDA normalized by 2n d equals the Gaussian gDoF defined in (3) in [START_REF] Wu | Interference channels with half-duplex source cooperation[END_REF], [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF], [START_REF] Yang | Interference channels with source cooperation in the strong cooperation regime: Symmetric capacity to within 2 bits/s/hz with dirty paper coding[END_REF]. The difference between our model and that of [START_REF] Avestimehr | Wireless network information flow: A deterministic approach[END_REF] is the inclusion of the binary-valued random variable M c to indicate the state of CTx [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF].

Very weak interference regime: α ∈ [0, 2/3). Without cooperation, i.e., β = 0, the tightest upper bound in this regime is (8c) [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF]. Recall that no-cooperation in equivalent to γ = 0, i.e., the cognitive source never listens to the channel. For a β > 0, the bound in (8c) is optimized by γ = 0, that is, by no-cooperation, whenever max{1, α, β} ≤ 2 max{1-α, α} = 2d (NoCoop) , which is equivalent to β ≤ 2d (NoCoop) . Intuitions suggest that the cooperation link gain should be "sufficiently strong" for HD unilateral cooperation to be beneficial. We can precisely quantify the statement "sufficiently strong" as follows: d > d (NoCoop) if β > 2d (NoCoop) . Recall that a strict inequality in the gDoF, or sum-capacity pre-log at high SNR, implies that the difference between the sum-capacities with HD unilateral cooperation and without cooperation becomes unbounded when SNR increases. In other words, when the cooperation link can reliably convey a rate larger than the sum-capacity of the non-cooperative IC (β > 2d (NoCoop) ), HD unilateral cooperation provides an unbounded sum-rate The optimal γ is obtained by equating the bounds in (8c) and (8b) and is given by

γ = min{2 -3α, α} min{2 -3α, α} + β -1 . (9)
We now give an intuitive argument for the optimal γ in (9). For the case 2 -3α ≤ α, i.e., α ∈ [1/2, 2/3), an achievable scheme for the LDA is represented in Fig. 2(a) and Fig. 2(c

= γ • 1 + (1 -γ) • (2 -2α) and R c /n d = γ • 0 + (1 -γ) • α, thus giving the sum- rate (R p + R c ) (IB) /n d = γ • 1 + (1 -γ) • (2 -α).
This sum-rate is larger than that without cooperation, given by 9) is smaller than 2-3α 1-α only if β > 2α. Thus, when β ≤ 2α, it would take too much time for the CTx to learn the message of the PTx and it is therefore better to not cooperate at all. The last observation gives an intuitive interpretation of why the gDoF in (8d) contains the term [β -2α] + for α ∈ [1/2, 2/3): the gDoF without cooperation is improved by HD unilateral cooperation only when β > 2d (NoCoop) = 2α.

2d (NoCoop) = 2α [4], if γ ≤ 2-3α 1-α . Next, γ in (
A similar reasoning may be done for the case 2 -3α > α, which corresponds to α ∈ [0, 1/2). For this regime an achievable scheme is given in Figs. 2(a) and 2(b), and the gDoF without cooperation is improved by HD unilateral cooperation only when β > 2d (NoCoop) = 2 -2α. The scheme for α ∈ [0, 1/2) is simpler than the one for α ∈ [1/2, 2/3) in that it only involves private messages. In particular, CTx sends the vector [b 4p + b 2 ] (i.e., b 4p is DPC-ed against b 2 ), of normalized length 1; PTx sends the vector [b 2 , b 3p , 0], whose components have normalized lengths α, 1 -2α and α, respectively; CRx decodes b 4p interference free because of DPC; PRx decodes b 2 and b 3p in this order; the optimal γ is such that the amount of b 2 -bits received by CTx in Phase 1 can be delivered to PRx in Phase 2, that is, γ(β -1) = (1γ)α thus giving the γ in (9) for α < 1/2; the achievable sum-rate is

(R p + R c ) (IB) /n d = γ • 1 + (1 -γ) • (2 -α).
Very strong interference regime: α ≥ 2. Without cooperation, i.e., β = 0, the tightest upper bound in this regime is (8a) [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF]. For a general β > 0, the bound in (8a) is optimized by γ = 0, which is equivalent to no-cooperation, whenever max{1, β} ≤ 2 = 2d (NoCoop) , which is equivalent to β ≤ 2d (NoCoop) . Again we see that HD unilateral cooperation is beneficial in terms of gDoF only when β is larger than the sum-gDoF without cooperation. Here the optimal γ is obtained by equating the bounds in (8a) and (8b) and given by

γ = α -2 β + α -3 . ( 10
)
To see why the optimal γ is given by ( 10), we again first analyze the LDA. Phase 1 is the same as in Fig. 2

= γ • 1 + (1 -γ) • (α -1) and R c /n d = γ • 0 + (1 -γ) • 1, giving a sum-rate of (R p + R c ) (IB) /n d = γ • 1 + (1 -γ) • α.
This sum-rate is larger than that without cooperation, given by 2d

(NoCoop) = 2 [4], if γ ≤ α-2 α-1 . Next, γ in (10) is smaller than α-2 α-1 only if β > 2.
Again, the interpretation is that, if β ≤ 2, it takes too long to transfer bits from PTx to CTx and hence it is preferable not to cooperate. This last observation gives an intuitive interpretation of why the gDoF in (8d) contains the term

[β -2] + for α ∈ [2, ∞): the gDoF without cooperation is improved only when β > 2d (NoCoop) = 2.
Moderately weak and strong interference regimes: For α ∈ [2/3, 2) and without cooperation β = 0 the upper bound in (8b) is the tightest [START_REF] Kramer | Outer bounds on the capacity of gaussian interference channels[END_REF]. The bound in (8b) is always optimized by γ = 0, which is equivalent to the case of no-cooperation. Hence, in this regime it is always gDoFoptimal to operate the channel as a non-cooperative IC and HD unilateral cooperation does not help in managing interference. It is very surprising that in this regime, no matter how strong the cooperation link is, unilateral causal cooperation cannot beat the performance of the non-cooperative system. In other words, d (NoCoop) = d (SYM) = d (Ideal) for α ∈ [2/3, 2). For α ∈ [2/3, 1), an optimal scheme for the LDA only uses b 3c , b 3p at PTx and b 4c , b 4p at CTx [START_REF] Bresler | The two-user gaussian interference channel: a deterministic view[END_REF]; for α ∈ [1, 2), b 3c at PTx and b 4c at CTx, both of normalized length α/2, are optimal [START_REF] Bresler | The two-user gaussian interference channel: a deterministic view[END_REF].

From the LDA to the AWGN: In Appendix B, we show Therefore, the LDA schemes in Fig. 2 tell us exactly: (a) how many Gaussian codewords must be superposed, with which power and at what rate, (b) if DPC is needed and if so against which interfering codeword, and (c) the decoding order at the receivers. With this, the achievable scheme is completely specified and the achievable rate can be computed. Comparisons: Fig. 3 shows the optimal gDoF and the gap for the interference-symmetric G-HD-CCIC. The whole set of parameters has been partitioned into multiple subregions depending upon different levels of cooperation (β) and interference (α) strengths. These regimes are numbered from 1 to 10, each discussed in Appendix A-A. We end this analysis with few comments: (i) everywhere, except in regions 3, 8 and 10 in Fig. 3, HD unilateral cooperation might not be worth implementing since the same gDoF is achieved without cooperation; (ii) the symmetric G-HD-CCIC attains the same gDoF of the non-causal G-CIC in regions 4 and 5 in Fig. 3. Thus, in these two regions, the performance of the system, in terms of gDoF, is not worsened by allowing causal learning at CTx; (iii) in regions 1, 4, 5 and 6 of Fig. 3 the gDoF equals that of the equivalent FD channel [START_REF] Cardone | On the interference channel with causal cognition[END_REF] and is equal to the non-cooperative case. Since the FD channel is an outer bound for the HD channel and no-cooperative strategies are possible under the HD constraint, we conclude that in these regimes the same gap results found for the FD case [START_REF] Cardone | On the interference channel with causal cognition[END_REF] hold in the case of HD source cooperation. In this case, gDoFwise, there is no loss in having a HD CTx compared to a more powerful FD CTx; (iv) all the achievable schemes use successive decoding at the receivers, which, in practice, is simpler than joint decoding. Thus our proposed schemes, which are optimal to within a constant gap, may be used as guidelines to deploy practical cognitive radio systems; (v) the gap computed in this work is around 2 bits larger than that computed in the corresponding FD case [START_REF] Cardone | On the interference channel with causal cognition[END_REF]. Possible ways to reduce the gap may be: (a) apply joint decoding at the receivers; (b) develop block Markov coding schemes instead of taking inspiration by the LDA; (c) develop achievable strategies that exploit the randomness into the switch to convey further useful information; (d) develop tighter upper bounds than those used in this work, especially for α ≤ 2/3 where the gap is quite large.

On numerical evaluation of the gap: The gap in Theorem 1 is pessimistic and it is due to the crude bounding of the upper and lower bounds, which seems to be necessary to obtain expressions that can be easily handled and compared analytically. In order to illustrate this point, in Fig. 4 we numerically evaluate the outer bound in (4) and the lower bound obtained from the scheme in Appendix B-C when the channel parameters fall into region 8 in Fig. 3, where the gap is the largest. By numerically optimizing all the optimization variables, i.e., power splits, correlation coefficients, fraction of time the CTx listens, we observe from Fig. 4 that the gap is of around 2.4 bits, i.e., more than 6 bits less than the analytical one. Although we can claim this gap reduction only for the simulated set of channel gains, we believe that this is a more general result.

V. THE Z-CHANNEL

In this section we analyze one of the two interferenceasymmetric G-HD-CCIC models: the Z-channel. With I p = 0 we obtain the Z-channel, for which we have Theorem 2. The sum-capacity upper bound in (4) is achievable to within 4.507 bits regardless of the actual value of the channel parameters for the Z-channel. Therefore, the gDoF can be obtained from (4) with I p = 0 and equals 3).

d (Z) = 1 2 max γ∈[0,1] min {γ max {1, β} + (1 -γ) 2, γ + (1 -γ) max {1, α} + [1 -α] + = max 1 -1 2 α, 1 2 α α ∈ [0, 2) 1 + 1 2 [β-2] + (α-2) β+α-3 α ∈ [2, ∞) . ( 11
)

Proof:

The details of the proof can be found in Appendix A-B.

For future reference, for the Z-channel

d (NoCoop) = min{1, max{1 -α/2, α/2}} ≤ d (Z) ≤ d (Ideal) = max{1 - α/2,
α/2} hence cooperation can only improve the gDoF in very strong interference, i.e., α > 2. The interpretation of the gDoF in ( 11) is similar to that of the interferencesymmetric case in (8d). In particular, if the channel has weak or strong interference, i.e., α ≤ 2, the gDoF is the same as for the non-cooperative Z-channel [START_REF] Sason | On achievable rate regions for the gaussian interference channel[END_REF]; in this regime it might not be worth to engage in unilateral cooperation. In very strong interference, i.e., α > 2, unilateral cooperation gives larger gDoF than in the case of no-cooperation only when β > 2d (NoCoop) = 2. An achievable scheme for the LDA in this regime is exactly the same developed for the corresponding interference-symmetric channel in Figs. 2(a) and 2(d), with the only difference that now the signal X p [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF] is not received at Y c [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF] since I p = 0.

Fig. 5 shows the optimal gDoF and the gap for the Zchannel. The whole set of parameters has been partitioned into multiple sub-regions depending upon different levels of cooperation (β) and interference (α) strengths. These regimes are numbered from 1 to 5 and the details for the gap computation appear in Appendix A-B. We conclude with few comments: (i) in regions 1, 4 and 5 of Fig. 5 the gDoF of the HD channel is as that in FD [START_REF] Cardone | On the interference channel with causal cognition[END_REF] and so the same gap results found for the FD case hold in the HD case. Moreover, in region 2 in Fig. 5 the gDoF equals that of the non-cooperative Z-channel. Hence, in regions 1, 2, 4 and 5 cooperation might not be worth implementing since the same gDoF is attained without cooperation; (ii) the Z-channel achieves the same gDoF of the non-causal cognitive Z-channel everywhere except in α > 2 (regions 1, 2 and 3 in Fig. 5), i.e., for α ≤ 2, causal cognition attains the ultimate performance of the ideal noncausal cognitive radio Z-channel; (iii) by comparing Figs. 3 and5, we observe that the gDoF of the Z-channel is always greater than or equal to that of the interference-symmetric channel. This is because the PTx does not cooperate in sending the message of CTx, i.e., by removing the link between PTx and CRx we rid CRx of only interfering signals. We observe that the Z-channel outperforms the interference-symmetric G-HD-CCIC when 0 ≤ α ≤ 2/3.

VI. THE S-CHANNEL

In this section we analyze the other interference-asymmetric G-HD-CCIC model: the S-channel. With I c = 0 we obtain the S-channel, for which we have Theorem 3. The sum-capacity upper bound in (4) is achievable to within 5 bits regardless of the actual value of the channel parameters for the S-channel. Therefore, the gDoF can be obtained from (4) with I c = 0 and equals

d (S) = 1 2 max γ∈[0,1] min {γ + 2 (1 -γ) , γ max {β, α, 1} + (1 -γ) max {1, α} + [1 -α] + =      1 -1 2 α + 1 2 α[α+β-2] + β+α-1 α ∈ [0, 1) 1 2 α + 1 2 (2-α)[β-α] + β-α+1 α ∈ [1, 2) 1 α ∈ [2, ∞) . ( 12
)
Proof: The details of the proof can be found in Appendix A-C.

For future reference, for the S-channel d (NoCoop) = min{1, max{1α/2, α/2}} ≤ d (S) ≤ d (Ideal) = 1 hence cooperation can improve performance only if the channel is not in very strong interference, i.e., α < 2. It is interesting to notice the different behavior of the Zand S-channel: for the Z-channel HD unilateral cooperation is useful only in very strong interference, while for the S-channel only when not in very strong interference. Also in this case the interpretation of the gDoF in ( 12) is similar to that of the interferencesymmetric case in (8d). In particular, if the channel has very strong interference, i.e., α > 2, the gDoF is the same as for the non-cooperative S-channel [START_REF] Sason | On achievable rate regions for the gaussian interference channel[END_REF]; in this regime it might not be worth to engage in unilateral cooperation. In weak and strong interference, i.e., α ≤ 2, unilateral cooperation gives larger gDoF than in the case of no-cooperation only when β > 2d (NoCoop) = 2 max{1α/2, α/2}. A representation of the LDA schemes used for α < 2 and β > 2 max{1α/2, α/2} is given in Figs. 2(a), 2(e) and 2(f), which can be interpreted as done for the interference-symmetric case in Fig. 2.

Fig. 6 shows the optimal gDoF and the gap for the Schannel. The whole set of parameters has been partitioned into multiple sub-regions depending upon different levels of cooperation (β) and interference (α) strengths. The details for the gap computation appear in Appendix A-C. We conclude the analysis of the S-channel with few comments: (i) there are some regions (1 and 2 in Fig. 6) in which the gDoF of the HD channel is as that in FD. In these regions, the same additive gap results found for the FD case [START_REF] Cardone | On the interference channel with causal cognition[END_REF] hold in HD. Moreover, in region 3 in Fig. 6 the gDoF equals that of the non-cooperative S-channel; (ii) the S-channel achieves the same gDoF of the non-causal cognitive S-channel, i.e., d = 1, for α ≥ 2 (region 1 in Fig. 6). Thus, in this region the S-channel attains the ultimate performance of the ideal non-causal cognitive radio S-channel; (iii) the S-channel outperforms the interferencesymmetric G-HD-CCIC when either 0 ≤ α ≤ 2/3 or when α ≤ 2 and β ≥ max{2α, α} (regions 4 and 5, and parts of regions 2 and 3 in Fig. 6). On the other hand, the interference-symmetric G-HD-CCIC outperforms the Schannel in very strong interference and strong cooperation, i.e., min{α, β} ≥ 2. This is so because, in the very strong interference and cooperation regime, the system performance is enhanced by allowing the CTx to help the PTx to convey the information to the PRx, but this is not possible since I c = 0; (iv) when α ≥ 2 (region 1 in Fig. 6) we have an exact sumcapacity result, i.e., the gap between the sum-rate outer bound and inner bound is equal to zero. Fig. 6: gDoF and constant gap for the interference-asymmetric S G-HD-CCIC.

VII. CONCLUSIONS

In this work we studied the Gaussian causal cognitive interference channel where the cognitive source, who helps the primary source, is constrained to operate in half-duplex mode. From an application standpoint, this model fits future 4G cellular networks with heterogeneous deployments. We analyzed both the interference-symmetric and interferenceasymmetric channels, which correspond to different network deployments. We determined, for each topology, the gDoF, the sum-capacity to within a constant gap and the optimal parameters in closed form. We compared the interferencesymmetric and interference-asymmetric models by highlighting the regimes where the gDoF is as that of the classical IC without cooperation, i.e., regimes where cooperation might not be worth implementing, and by identifying the regimes where the system attains the ultimate limits predicted by the ideal non-causal cognitive model, i.e., regimes where the performance is not worsened by allowing causal half-duplex learning at the cognitive source. Extensions to the general channel and to the whole capacity region characterization to within a constant gap are subjects of current investigation. Outer Bound: in this regime the tightest sumrate outer bound is given by ( 5), which can be further upperbounded as (R p + R c ) (OB) ≤ 2.507 + 2 log (1 + S). Thus, GAP ≤ 2.507 bits.

Regime 3: Very Strong Interference 3: α ≥ 2, β > 2. Parameter Range: I ≥ S(1 + S) and C > S(S + 1), where we have 2d ≤ max γ min {γβ + 2 (1γ) , γ + (1γ) α}. In this expression the first term is increasing in γ while the second one is decreasing in γ. Thus the optimal γ can be found by equating the two terms and is given by γ = α-2 β+α-3 in [START_REF] Yang | Interference channel with generalized feedback (a.k.a. with source cooperation): Part i: Achievable region[END_REF], which leads to d ≤ 1 6) are the tightest outer bounds. With [START_REF] Devroye | Achievable rates in cognitive radio channels[END_REF], GAP ≤ 3.507 bits; with (6), GAP ≤ 5 bits. Thus, GAP ≤ 5 bits.

Regime 4: Strong Interference: 1 ≤ α < 2. Parameter Range: S ≤ I < S(1 + S), in which case d ≤ α 2 (with γ = 0). The gDoF upper bound coincides with that in FD [START_REF] Cardone | On the interference channel with causal cognition[END_REF], so GAP ≤ 1 bit.

Regime 5: Moderately Weak Interference: 2/3 ≤ α < 1. Parameter Range: I < S and S(S + 1) ≤ I(I + 1) 2 , in which case d ≤ 1-α 2 (with γ = 0). The gDoF upper bound coincides with that in FD [START_REF] Cardone | On the interference channel with causal cognition[END_REF]. Thus, as in FD, GAP ≤ 3 bits. S , in which case we have d ≤ α (with γ = 0). The gDoF upper bound coincides with that in FD [START_REF] Cardone | On the interference channel with causal cognition[END_REF]. Thus, as in FD, GAP ≤ 6.32 bits.

Regime 7: Weak Interference 2: 1/2 ≤ α < 2/3, 2α-1 < β ≤ 2α. Parameter Range: S(S + 1) > I(I + 1) 2 , S ≤ I (1 + I) and I 2 S < C ≤ I 2 , where we have d ≤ α (with γ = 0). Inner Bound: classical IC with the power split of [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF], i.e., (R p + R c )

(IB) = 2 log 1 + I + S I -2, which implies d = α. Outer Bound: in this regime the tightest sum-rate outer bound is given by [START_REF] Host-Madsen | Capacity bounds for cooperative diversity[END_REF], that can be further upper bounded as (R p + R c ) (OB) ≤ 3.5048 + 2 log 1 + I + S I . Thus, GAP ≤ 5.5048 bits.

Regime 8: Weak Interference 3: 1/2 ≤ α < 2/3, β > 2α. Parameter Range: S(S + 1) > I(I + 1) 2 , S ≤ I (1 + I) and C > I 2 , in which case 2d ≤ max γ min {γ + (1γ) (2α) , γβ + 2 (1γ) α}. In this expression the first term is decreasing in γ while the second term is increasing in γ. Thus the optimal γ can be found by equating the two terms and is given by γ = 2-3α β-3α+1 in [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF], which leads to d ≤ 1 2 2β-αβ-2α β-3α+1 . Inner Bound: the rate in [START_REF] Mirmohseni | On the capacity of interference channel with causal and noncausal generalized feedback at the cognitive transmitter[END_REF] at the top of next page is achievable (Appendix B-C), where γ =

x log(1+ C 1+S )+x SNR 1 → γ for x := log 1 + S 2 (1+I) 3 +S+SI SNR 1 → 2 -3α. The sum-rate in (14) implies 2d = 2-3α β-3α+1 [1 -0 + (β -1)] + β-1 β-3α+1 [2α -0 + (1 -α) -(1 -α)] = 2β-αβ-2α
β-3α+1 . Outer Bound: in this regime the tightest sum-rate outer bounds are those in ( 6) and [START_REF] Host-Madsen | Capacity bounds for cooperative diversity[END_REF]. With the bound in [START_REF] Rini | Inner and outer bounds for the gaussian cognitive interference channel and new capacity results[END_REF], GAP ≤ 8 bits; with the bound in [START_REF] Host-Madsen | Capacity bounds for cooperative diversity[END_REF], GAP ≤ 8.5048 bits. Thus, GAP ≤ 8.5048 bits.

Regime 9: Weak interference 4: α < 1/2, β ≤ 2 -2α. Parameter Range: I(I + 1) < S and C ≤ S 2 I 2 , in which case we have d ≤ 1α (with γ = 0). Inner Bound: classical IC, i.e., (R p + R c )

(IB) = 2 log 1 + S 1+I , which implies d = 1α. Outer Bound: the tightest sum-rate outer bound is given by [START_REF] Host-Madsen | Capacity bounds for cooperative diversity[END_REF], that can be further upper bounded as

(R p + R c ) (OB) ≤ 3.5048 + 2 log 1 + I + S I . Thus GAP ≤ 3.5048 + 2 log 1+I I + 2 log I 2 +I+S 1+I+S ≤ 3.5048 + 4 log (2) = 7.5048 bits. (R p + R c ) (IB) = γ log (1 + S) -log 1 + S 1 + S + γ log 1 + C 1 + S + 2 (1 -γ ) log (1 + S) (13)
(R p + R c ) (IB) = γ log (1 + S) -γ log 1 + S 1 + S + γ log 1 + C 1 + S + 2 (1 -γ ) log 1 + I + S 1 + I -(1 -γ ) 2 log 1 + I 1 + I -log 1 + S 1 + I + I 1 + I -(1 -γ ) log 1 + SI + I + I 2 (1 + I) 2 + S 1 + I (14) (R p + R c ) (IB) = γ log (1 + S) -γ log 1 + S 1 + S + γ log 1 + C 1 + S -(1 -γ ) log (1 + I) + (1 -γ ) log 1 + I + S 1 + I -(1 -γ ) log 1 + I 1 + I + (1 -γ ) log 1 + I 1 + I + S ( 15
) (R p + R c ) (IB) = log (1 + S) -γ log 1 + S 1 + S + γ log 1 + C 1 + S + (1 -γ ) log (1 + S + I) -(1 -γ ) log 1 + SI 1 + I + S ( 16
) (R p + R c ) (IB) = γ log (1 + S) -γ log 1 + S 1 + S + γ log 1 + C 1 + S + (1 -γ ) log 1 + S 1 + I + (1 -γ ) log 1 + S + I 1 + I -(1 -γ ) log 1 + I 1 + I (17) Regime 10: Weak Interference 5: α < 1/2, β > 2 -2α. Parameter Range: I(I + 1) < S and C > S 2 I 2 , in which case we have 2d ≤ max γ min {γ + (1 -γ) (2 -α) , γβ + 2 (1 -γ) (1 -α)}.
In this expression the first term is decreasing in γ while the second term is increasing in γ. So the optimal γ can be found by equating the two terms and is given by γ =

implies 2d = α β+α-1 [1 -0 + (β -1)] + β-1 β+α-1 [-α + (1 -α) + 1 -0] = 2β+2α-αβ-2 β+α-1
. Outer Bound: (6) and ( 7) are the tightest. With (6), GAP ≤ 6 bits; with (7), GAP ≤ 7.5048 bits. Thus, GAP ≤ 7.5048 bits.

B. Z-channel

Let I c = I, I p = 0 and d (Z) = d for brevity. We consider two different regimes.

Regime 1: Strong and Very Strong Interference: α ≥ 1. The analysis is similar to that of the interference-symmetric G-HD-CCIC in the same regime (same inner and outer bounds with I p = 0) and the gap is at most 4.507 bits. In regions 1 and 4 in Fig. 5, then, the gDoF upper bound coincides with that in FD [START_REF] Cardone | On the interference channel with causal cognition[END_REF]. Thus in these two regions, as in FD, GAP ≤ 1 bit.

Regime 2: Weak Interference: α < 1, in which case d ≤ 1 -α 2 (with γ = 0). The gDoF outer bound coincides with that in FD [START_REF] Cardone | On the interference channel with causal cognition[END_REF]. Thus, as in FD, GAP ≤ 1 bit.

C. S-channel

Let I p = I, I c = 0 and d (S) = d for brevity. We analyze different regimes.

Regime 1: Very Strong Interference: α ≥ 2. The gDoF is as for the non-cooperative S-channel. In this regime the gDoF upper bound coincides with that in FD [START_REF] Cardone | On the interference channel with causal cognition[END_REF], so GAP = 0 bit.

Regime 2: α < 2 and β ≤ max {1, α}. In this regime the gDoF is as for the non-cooperative S-channel. The gDoF upper bound coincides with that in FD [START_REF] Cardone | On the interference channel with causal cognition[END_REF]. Thus, as in FD, GAP ≤ 2 bits. (IB) = log (1 + S) + log 1 + S 1+I , which implies d = 1-1 2 α. Outer Bound: in this regime the tightest sumrate outer bound is given by [START_REF] Rini | Inner and outer bounds for the gaussian cognitive interference channel and new capacity results[END_REF], that can be further bounded as

(R p + R c ) (OB) ≤ 2 + log 1 + √ I + √ S 2 + log S I . Thus GAP ≤ 2 + log 1 + 2 √ SI 1+I+S + log 1 + 1 I ≤ 4 bits. Regime 4: Strong Interference: 1 ≤ α < 2, β > α.
Parameter Range: S ≤ I < S(S + 1) and C > I, in which case we have 2d ≤ max γ min {γ + 2 (1γ) , γβ + (1γ) α} . In this expression the first term is decreasing in γ while the second term is increasing in γ. Thus the optimal γ can be found by equating the two terms and is given by γ = 2-α β-α+1 , which leads to d ≤ 1 2 2β-α β-α+1 . Inner Bound: inspired by the LDA scheme in Figs. 2(a) and 2(f) (which can be inferred from that in Fig. 2(c) with different power splits), the rate in [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF] at the top of the page, with γ =

x log(1+ C 1+S )+x SNR 1 → γ for x := log 1 + S 2 1+I SNR 1 → 2 -α, is achievable The sum-rate in (16) implies 2d = 1+ 2-α β-α+1 [-0+(β-1)]+ β-1 β-α+1 [α-1] = 2β-α β-α+1
min {γ + 2 (1 -γ) , γβ + (1 -γ) (2 -α)} .
In this expression the first term is decreasing in γ while the second term is increasing in γ. Thus the optimal γ can be found by equating the two terms and is given by γ = α β+α-1 , which leads to d ≤ 1 With the first constraint in [START_REF] Rini | Inner and outer bounds for the gaussian cognitive interference channel and new capacity results[END_REF], GAP ≤ 4 bits; with the second one in [START_REF] Rini | Inner and outer bounds for the gaussian cognitive interference channel and new capacity results[END_REF], GAP ≤ 5 bits. Thus, GAP ≤ 5 bits.

APPENDIX B

Here we develop achievable schemes inspired by Fig. 2. In the following all signals X bj for some subscript j, are independent proper-complex Gaussian random variables with zero mean and unit variance and represent codebooks used to convey the bits in b j in Fig. 2.

A. Phase 1 of duration γ ∈ [0, 1] (see also Fig. 2(a))

The transmitted signals are X p [START_REF] Cardone | The symmetric sum-capacity of the gaussian half-duplex causal cognitive interference channel to within a constant gap[END_REF] = √ 1 -ηX b1 + √ ηX b2 , with η := 1 1+S and X c [1] = 0. CTx applies successive decoding of X b1 followed by X b2 from Y f [START_REF] Cardone | The symmetric sum-capacity of the gaussian half-duplex causal cognitive interference channel to within a constant gap[END_REF] which is possible if

R b1 ≤ γ log (1 + C) -γ log 1 + C 1 + S R b2 ≤ γ log 1 + C 1 + S . (18)
PRx decodes X b1 treating X b2 as noise from Y p [START_REF] Cardone | The symmetric sum-capacity of the gaussian half-duplex causal cognitive interference channel to within a constant gap[END_REF] which is possible if

R b1 ≤ γ log (1 + S) -γ log 1 + S 1 + S . (19)
Since C > S, Phase 1 is successful if [START_REF] Wu | Interference channels with half-duplex source cooperation[END_REF] and ( 19) are satisfied.

B. Phase 2 of duration (1γ) for Region 3 in Fig. 3 (see also Fig. 2(d))

The transmit signals are X p [2] = X b3c and X c [2] = √ ηX b2 + √ 1 -ηX b4c , with η = 1 1+S . PRx applies successive decoding as follows: X b4c , X b2 , X b3c from Y p [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF], which is possible if

R b4c ≤ (1-γ) log (1+S+I)-log 1+ I 1+S +S (20)
R b2 ≤ (1 -γ) log 1 + I (1 + S) 2 (21)
R b3c ≤ (1 -γ) log (1 + S) . ( 22
)
CRx successively decodes X b3c and X b4c (treating X b2 as noise) from Y c [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF], which is possible if

R b3c ≤ (1 -γ) log (1 + S + I) -(1 -γ) log (1 + S) (23)
R b4c ≤ (1 -γ) log (1 + S) -(1 -γ) log 1+ S 1+S . ( 24
)
Phase 2 is successful if min{eq. [START_REF] Kramer | Outer bounds on the capacity of gaussian interference channels[END_REF],eq.( 23)} = eq.( 22), min{eq. [START_REF] Sason | On achievable rate regions for the gaussian interference channel[END_REF],eq.( 20)} = eq.( 24) and eq.( 21), are satisfied. By imposing that R b2 is the same in both phases, i.e., that [START_REF] Wu | Interference channels with half-duplex source cooperation[END_REF] and ( 21) are equal, we get that γ should be chosen equal to γ =

x log(1+ C 1+S )+x , x := log 1 + I (1+S) 2 . Therefore the total sum-rate decoded at PRx and CRx through the two phases is (R p + R c )

(IB) = R b1 + R b2 + R b3c + R b4c as given in [START_REF] Yang | Interference channels with source cooperation in the strong cooperation regime: Symmetric capacity to within 2 bits/s/hz with dirty paper coding[END_REF].

C. Phase 2 of duration (1γ) for Region 8 in Fig. 3 (see also Fig. 2(c))

The transmitted signals are

X p [2] = δ 1 X b3c + δ 2 X b2 + δ 3 X b3p X c [2] = δ 3 X b4p + 1 -δ 3 X b4c with δ 1 = 1 -δ 2 -δ 3 , δ 2 = S (1+I) 2 , δ 3 = 1 1+I
, where X b4p is DPC-ed against X b2 at Y c [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF]. PRx applies successive decoding as follows: X b3c , X b2 , X b4c and X b3p (treating X b4p as noise) from Y p [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF], which is possible if

Thus, since we are in the regime I(1 + I) 2 < S(S + 1), Phase 2 is successful if (25), ( 26), ( 27), ( 28) and (29) are satisfied. By imposing that R b2 is the same in both phases, that is, that [START_REF] Wu | Interference channels with half-duplex source cooperation[END_REF] and ( 25) are equal, we get that γ should be chosen equal to γ =

x log(1+ C 1+S )+x , x := log 1 + S 2 (1+I) 3 +S+SI . With this scheme, the total sum-rate decoded at PRx and CRx through the two phases is (R p + R c )

(IB) = R b1 + R b3c + R b3p + R b2 + R b4c + R b4p as given in [START_REF] Mirmohseni | On the capacity of interference channel with causal and noncausal generalized feedback at the cognitive transmitter[END_REF]. D. Phase 2 of duration (1γ) for Region 10 in Fig. 3 (see also Fig. 2(b))

The transmitted signals are

X p [2] = √ 1 -δX b2 + √ δX b3p with δ = 1
1+I and X c [2] = X b4p , which is DPC-ed against X b2 at Y c [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF]. PRx decodes X b2 and X b3p in this order (by treating X b4p as noise) from Y p [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF], that is possible if

R b2 ≤ (1-
+ R c ) (IB) = R b1 + R b3p + R b2 + R b4p
as given in [START_REF] Cardone | On the interference channel with causal cognition[END_REF].

Fig. 1 :

 1 Fig. 1: The G-HD-CCIC. Left: symmetric channel. Center: Z-channel. Right: S-channel.

  Phase 1 (Mc = 0) common to the the symmetric and asymmetric channels.

  Phase 2 (Mc = 1) for α ∈ [0, 1/2) for the symmetric channel.

  Phase 2 (Mc = 1) for α ∈ [1/2, 2/3) for the symmetric channel. Phase 2 (Mc = 1) for α ∈ [2, ∞) for the symmetric channel. Phase 2 (Mc = 1) for α ∈ [0, 1) for the Schannel. Phase 2 (Mc = 1) for α ∈ [1, 2) for the Schannel.

Fig. 2 :

 2 Fig. 2: Achievable strategies for the symmetric and asymmetric LDA channels.

) for the case β ≥ 1 .

 1 The bit vectors (b 1 , b 2 , b 3 ) are from PTx to PRx, and the bit vector b 4 from CTx to CRx. Since the CTx can only either receive or transmit at any point in time, we divide the transmission into two phases. Phase 1: for a fraction γ ∈ [0, 1] of the time CTx listens to the channel and PTx sends (b 1 , b 2 ); b 1 is decoded by PRx and b 2 is decoded only at CTx. Phase 2: for the remaining fraction 1γ of the time CTx transmits; PTx sends (b 2 , b 3 ) and CTx sends (b 2 , b 4 ) -notice that PTx and CTx cooperate in sending b 2 , which hence is a cooperative message. The vectors b i , i ∈ {3, 4}, are split into a common message (b ic ), decoded also at the non-intended receiver, and a private message (b ip ), treated as noise at the non-intended receiver. More specifically, in Phase 1 in Fig. 2(a) CTx listens to the channel and PTx sends the vector [b 1 , b 2 ], where b 1 has normalized (by the direct link gain n d ) length 1 and b 2 has normalized length β -1 (for a total normalized length of 1 + (β -1) = β = max{1, α, β}). Hence, over a fraction γ of the transmission time, CTx receives γ(β -1) b 2 -bits that PRx In each sub-figure of Fig. 2, on the left hand side we represent the transmitted signals Xp and Xc, which are vectors of normalized length n/n d = max{1, α, β}, and on the right hand side the received signals Yp and Yc, which are vectors of normalized length max{1, α} and are the sum of a certain down shifted version of the transmitted vectors.After the downshift operation, the top part of a vector would be populated by zero; we do not represent these zeros and instead leave an empty space in order not to clutter the figure. Note that the bits received at the same level at a node must be summed modulo-two.has not received yet. In Phase 2, CTx assists PTx to deliver these b 2 -bits to PRx in either of the two following cooperation modes: (i) CTx relays the b 2 -bits to PRx on behalf of PTx by spending some of its own resources, (ii) CTx treats the b 2 -bits as a 'state non-causally known at the transmitter but unknown at the receiver' and precodes its transmitted signal against it.Phase 2 in Fig.2(c): CTx sends the vector [b 4c , 0, b 4p + b 2 ], whose components have normalized lengths 2α -1, 1α and 1α, respectively. In the LDA, the linear combination b 4p + b 2 can be thought of as pre-coding the signal b 4p against the interference caused by b 2 . PTx sends the vector [b 3c , b 2 , 0, b 3p ], whose components have normalized lengths 2α-1, 2-3α, 2α-1 and 1-α (with an abuse of notation, here b 2 indicates the bits that have been received in Phase 1 at CTx), respectively. CRx successively decodes b 4c , b 3c , b 4p in this order, while PRx successively decodes b 3c , b 2 , b 4c , b 3p in this order. Notice that CRx does not experience interference from b 2 when decoding b 4p (recall that on GF(2) 1+1 = 0+0 = 0). The achievable rates are R p /n d

  (a). In Phase 2 / Fig. 2(d), CTx sends [b 4c , b 2 , 0], whose components have normalized lengths 1, α -2, and 1 (here b 2 indicates again, with an abuse of notation, the bits that have been received in Phase 1 at CTx), respectively. PTx sends [b 3c , 0], whose components have normalized lengths 1 and α -1, respectively. CRx successively decodes b 3c , b 4c in this order. PRx successively decodes b 4c , b 2 , b 3c in this order. The achievable rates are R p /n d

Fig. 3 :

 3 Fig. 3: gDoF and constant gap for the interference-symmetric G-HD-CCIC.

Fig. 4 :

 4 Fig.4: Numerical evaluation of the gap for the symmetric G-HD-CCIC with α = 0.55 and β = 2 (Region 8 in Fig.3).

Fig. 5 :

 5 Fig. 5: gDoF and constant gap for the interference-asymmetric Z G-HD-CCIC.

ACKNOWLEDGMENT

  The work of D. Tuninetti was partially funded by NSF under award number 0643954; the contents of this article are solely the responsibility of the authors and do not necessarily represent the official views of the NSF. Eurecom's research is partially supported by its industrial partners: BMW Group Research & Technology, IABG, Monaco Telecom, Orange, SAP, SFR, ST Microelectronics, Swisscom and Symantec. The research carried out at Eurecom leading to these results has received funding from the EU Celtic+ Framework Program Project SPECTRA. The research at IMC leading to these results has received funding from the EU FP7 project iJOIN, grant agreement n • 317941. APPENDIX A A. Interference-symmetric G-HD-CCIC Let I p = I c = I and d (SYM) = d for brevity. We analyze the different regimes in Fig. 3. Regime 1: Very Strong Interference 1: α ≥ 2, β ≤ 1. Parameter Range: I ≥ S(1 + S) and C ≤ S, in which case we have d ≤ 1 (with γ = 0), as in FD. Thus, as in FD, GAP ≤ 1 bit. Regime 2: Very Strong Interference 2: α ≥ 2, 1 < β ≤ 2. Parameter Range: I ≥ S(1+S) and S < C ≤ S(S+1), in which case d ≤ 1 (with γ = 0). Inner Bound: classical IC in very strong interference, i.e., (R p + R c ) (IB) = 2 log (1 + S), which implies d = 1.

2 βα- 2 β+α- 3 . 1 →(1+S) 2 SNR 1 → 1 → 1 β+α- 3 [ 1 + 1 -

 22312111311 Inner Bound: The achievable scheme in Appendix B-B, with γ = x log(1+ C 1+S )+x SNR γ for x := log 1 + I α -2 (recall that log 1 + C 1+S SNR β -1), gives (13) at the top of next page, which implies 2d = α-2 β+α-3 [1 -0 + (β -1)] + β-0] = αβ-2 α+β-3 . Outer Bound: (5) and (

Regime 6 :

 6 Weak Interference 1: 1/2 ≤ α < 2/3, β ≤ 2α -1. Parameter Range: S(S + 1) > I(I + 1) 2 , S ≤ I (1 + I) and C ≤ I 2

1 . 1 →

 11 Inner Bound: the sum-rate in[START_REF] Cardone | On the interference channel with causal cognition[END_REF] at the top of the page is achievable (Appendix B-D), where γ = α. The sum-rate in[START_REF] Cardone | On the interference channel with causal cognition[END_REF]

Regime 3 :

 3 Weak Interference 1: α < 1, 1 < β ≤ 2α. Parameter Range: I < S and S < C ≤ S 2 I , in which case we have d = 1 -α 2 (with γ = 0). Inner Bound: classical noncooperative S-channel in weak interference [24, Theorem 2], i.e., (R p + R c )

2 2β+α- 2 β+α- 1 . 1 →γ 1 →

 22111 Inner Bound: inspired by the LDA scheme in Figs.2(a) and 2(e) (which can be inferred from that in Fig.2(b) with different power splits), the rate in[START_REF] Cardone | Gaussian halfduplex relay channels: Generalized degrees of freedom and constant gap result[END_REF] at the top of the previous page, with γ =x log(1+ C 1+S )+x SNR , with x := log 1 + SI 1+S+I SNR min{1, α} = α, is achievable. The sum-rate in (17) implies 2d = α β+α-1 [1 -0 + (β -1)] + β-1 β+α-1 [(1α) + 1 -0] = 2β+α-2 β+α-1 .Outer Bound: the tightest sum-rate outer bound is that in (6) (with I c = 0).

R 1 + I) 2 R 1 + I) 2 -( 1 -

 12121 b3c ≤ (1γ) log (1 + S + I) -(1γ) log 1 + I + S 2 + SI + S (b2 ≤ (1γ) log 1 + I + S 2 + SI + S (γ) log 1 + I + S 1 + I (25) R b4c ≤ (1γ) log 1 + I + S 1 + I -(1γ) log 1 decoding as follows: X b4c , X b3c and X b4p from Y c [2], which is possible if R b4c ≤ (1γ) log (1 + S + I)log 1 + I + S 1 + I R b3c ≤ (1γ) log 1 + I + S 1 + I -(1γ) log 1 + SI + I + I 2 (1 + I) 2 + S 1 + I (28) R b4p ≤ (1γ) log 1 + S 1 + I + I 1 + I -(1γ) log 1 + I 1 + I .

  Regime 5: Weak Interference 2: α < 1, β > 2α. Parameter Range: I < S and C > S 2I , in which case we have 2d ≤ max γ

. Outer Bound: the tightest sum-rate outer bound is that in (6) (with I c = 0). With the first constraint in

[START_REF] Rini | Inner and outer bounds for the gaussian cognitive interference channel and new capacity results[END_REF]

, GAP ≤ 4 bits; with the second one in

[START_REF] Rini | Inner and outer bounds for the gaussian cognitive interference channel and new capacity results[END_REF]

, GAP ≤ 4 bits. Thus, GAP ≤ 4 bits.

  CRx decodes X b4p (by treating X b3p as noise) from Y c[START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (EUTRA)[END_REF], which is possible if Thus Phase 2 is successful if (30), (31) and (32) are satisfied. By imposing that R b2 is the same in both phases, that is, that (18) and (30) are equal, we get that γ should be chosen equal to γ = +S . With this scheme, the total sum-rate decoded at PRx and CRx through the two phases is (R p

	γ) log (1+S+I)-log 1+I+	S 1 + I	(30)
	R b3p ≤ (1 -γ) log 1 + I +	S 1 + I	-log (1 + I) . (31)
	R b4p ≤ (1-γ) log 1+S+	I 1+I	-log 1+	I 1+I	. (32)
	x log(1+ C 1+S )+x	, x := log 1 +	SI (1+I) 2