{'fraction_non_alphanumeric': 0.04509813382872722, 'fraction_numerical': 0.011906341604641905, 'mean_word_length': 4.084956295046772, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 42, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 33, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Interference Mitigation in Large Random Wireless Networks

A central problem in the operation of large wireless networks is how to deal with interference -- the unwanted signals being sent by transmitters that a receiver is not interested in. This thesis looks at ways of combating such interference. In Chapters 1 and 2, we outline the necessary information and communication theory background, including the concept of capacity. We also include an overview of a new set of schemes for dealing with interference known as interference alignment, paying special attention to a channel-state-based strategy called ergodic interference alignment. In Chapter 3, we consider the operation of large regular and random networks by treating interference as background noise. We consider the local performance of a single node, and the global performance of a very large network. In Chapter 4, we use ergodic interference alignment to derive the asymptotic sum-capacity of large random dense networks. These networks are derived from a physical model of node placement where signal strength decays over the distance between transmitters and receivers. (See also arXiv:1002.0235 and arXiv:0907.5165.) In Chapter 5, we look at methods of reducing the long time delays incurred by ergodic interference alignment. We analyse the tradeoff between reducing delay and lowering the communication rate. (See also arXiv:1004.0208.) In Chapter 6, we outline a problem that is equivalent to the problem of pooled group testing for defective items. We then present some new work that uses information theoretic techniques to attack group testing. We introduce for the first time the concept of the group testing channel, which allows for modelling of a wide range of statistical error models for testing. We derive new results on the number of tests required to accurately detect defective items, including when using sequential `adaptive' tests.


Introduction
A central problem in the operation of large wireless networks is how to deal with interference -the unwanted signals being sent by transmitters that a receiver is not interested in. This thesis looks at ways of combating such interference in large random wireless netoworks.
In Chapter 1: Information, we briefly summarise information theory in the single user (point-to-point) case.
A channel models how signals are corrupted by noise. We pay particular attention to the Gaussian channel, which is a good model for real-world wireless communication, and the finite field channel, which can be thought of as a discretisation of the Gaussian channel The capacity of a channel tells us how much information we can send through the channel for an arbitrarily low probability of error. Shannon's channel coding theorem tells us how to calculate the capacity of a channel. We also demonstrate the capacity of the Gaussian channel under a power constraint.
Fading models how signals can decay and distort when sent over long distances. We investigate three types of fading -fixed, slow, and fast -and show how they affect the channel capacity.
In Chapter 2: Interference, we extend our study to multiuser networks.
We look at information theoretic models of wireless networks, concentrating on the interference network, where many transmitter-receiver pairs want to communicate through the same medium. This network suffers from the problem of interference.
Weak interference can be ignored and treated as background noise, while strong interference can be decoded and subtracted. The main problem for networks is interference of a similar strength to the desired signal.

Introduction
We look at resource division strategies, which share the channel resources between the users. While such schemes are simple to operate, they perform poorly when the number of users is high.
Of more interest are new interference alignment strategies. These work by the following idea: if transmitters plan their signals carefully, then for each receiver the interfering signals can be aligned together, with the desired signal split off separately. Interference alignment techniques offer potentially far higher performance than resource division schemes. We pay particular attention to a channel state-based strategy called ergodic interference alignment.
Chapter 3: Regular and Poisson random networks, shows how a simple interference-as-noise technique can be useful when communicating over short hops in well-structured networks.
In a d-dimensional regular network, nodes are placed on the grid Z d . We show that if signals decay like distance −α for α > d, then all nodes can communicate at some fixed rate r. We call this linear growth, as the sum-rate of communication of a collection of nodes scales linearly with the number of nodes.
We also look at nearest-neighbour communication in Poisson random networks, where nodes are placed at random like a Poisson point process. We give bounds on the outage probability, the chance that a given link is unable to communicate at some fixed rate. We also show that linear growth occurs with probability tending to 1.
This chapter is joint work with Oliver Johnson and Robert Piechocki.
In Chapter 4: Sum-capacity of random dense Gaussian interference networks, we consider spatially separated IID networks with power-law attenuation, a natural model for wireless networks. We derive the asymptotic sum-capacity of such networks by using ergodic interference alignment to show achievability, and subtle probabilistic and counting techniques to show the converse. We also give an alternative proof (with an improved rate of convergence) to a recent theorem of Jafar on the sum-capacity of large random networks.
This chapter is joint work with Oliver Johnson and Robert Piechocki. This research has been published in IEEE Transactions on Information Theory [1], and in the Proceedings of the 2010 IEEE International Symposium on Information Theory [2].
Chapter 5: Delay-rate tradeoff in ergodic interference alignment considers the long blocklengths required to perform ergodic interference alignment. We outline a new scheme called JAP(a) and study a beamforming extension and derived child schemes.
We show how to reduce the time delay for full performance of ergodic interference alignment. We also show how delay can be reduced even further for the tradeoff of a decrease in communication rate. We analyse the best schemes for small networks, and as the size of the network tends to infinity.
This chapter is joint work with Oliver Johnson and Robert Piechocki. This research has been submiited to IEEE Transactions on Communication Theory -a preprint is available on the arXiv [3].
We begin Chapter 6: Interference, group testing, and channel coding by considering a problem where receivers must aim to detect which transmitters interfere with them. We show that our formulation of this problem is equivalent to the problem of combinatorial group testing.
Recent work by Atia and Saligrama has shown how channel coding techniques can shed light on the problem of group testing. We extend their results, by defining group testing channels, and identifying the only-defects-matter property, under which an important theorem holds.
We give the first information theoretic analysis of adaptive group testingswhere test pools can be constructed sequentially based on previous outcomes -by drawing a comparison with the problem of channel coding with feedback.
The thesis finishes with Chapter 7: Conclusions and further work. In this chapter, we examine the subject of information theory, and in particular channel coding, which forms the mathematical basis for studying communication.
We start by giving a brief overview of the subject, and making note of a 'handbook' of useful definitions and facts. We then go through the more formal mathematics of point-to-point communication, concentrating on accurate models for real-life wireless communication. Finally, we study fading, which allows us to model how signals distort as passed through space.

Information theory: a very short introduction
Information theory is the mathematical framework used for studying the transmission of messages in the presence of noise. It was founded by Claude Shannon in his seminal paper of 1948, "A mathematical theory of communication" [4]. Shannon's information theory involves the sending of a message -information that a transmitter (typically called Alice) might wish a receiver (Bob) to know -through a channel, such as a telephone line, an internet connection or a computer cable.

Chapter 1. Information
The method, language or standard used to transfer the message is called the code. (We use 'code' in the sense of 'Morse code' -there is no intention to keep the transmitted signal secret as well.) One of the major goals of information theory involves quantifying how much information can be sent down a channel and how quickly. For example, if Alice wants to arrange a meeting with Bob, she might send the message "Hi Bob, meet me at five o'clock on Monday." But if the line is very crackly, Bob might interpret the message incorrectly: "Hi Bob, meet me at nine o'clock on Sunday." How could Alice ensure that this doesn't happen? Perhaps Alice could use a code where she repeats the sentence a number of times, hoping that it would be more likely that Bob could deduce the intended message. But this takes a longer amount of time -we say that her rate of communication is very low -and phone calls are expensive, making this undesirable.
Unsurprisingly, there is a trade-off to be made between the rate at which Alice can send the information and the probability that Bob receives it without error. Before Shannon, it was widely assumed that the only way to make the error probability as small as desired was to reduce the rate of communication toward zero too [5,Section 5.1]. However, Shannon discovered that, while this trade-off certainly exists, the error probability can made arbitrarily small while maintaining a communication rate bounded away from zero. Error probability In other words, there is a cutoff rate c such that if we attempt to send information at a rate r < c, we can do so with an arbitrarily low risk of error, whereas if we attempt to send information at a rate r > c, the probability of error is bounded away from 0. Shannon called this cutoff rate c the capacity of the channel.
-Error-free communication at rates r < c 0 c Errors at rates r > c r Shannon managed to calculate the capacity of a number of communication channels in terms of the statistical properties of the noise in a channel. The result is known as Shannon's channel coding theorem (and is stated as Theorem 1.11 later).
The aim of this thesis is to find bounds and approximations for capacities of complicated multi-user networks. In particular, we will be interested in networks that model large real-world wireless networks, such as WiFi computer networks or BlueTooth.
The capacity of a channel, such as a wireless link, tells us the maximum rate at which we can send information while being assured the messages are received accurately. Note however that merely knowing the capacity does not give us a method of achieving communication at, or even near, capacity. Nonetheless, the capacity is still a useful benchmark for the quality of a channel. First, it gives us a 'best case' against which we can compare any technologies: if a new code allows us to communicate at a rate near capacity, then this technology is about as good as it's going to get, and there is no need to spend more money on research. Second, studying the mathematical form of the capacity may help us improve the channel itself; for instance, whether extra resources would be best spent increasing power, bandwidth, or the number of antennas.

Handbook of useful facts
The following basic concepts of information theory will be referred to often in this thesis; we collect them here for reference.
More information is available in any basic information theory textbook -Cover and Thomas's Elements of Information Theory [6] is a favourite of mine.
Mass and density functions. For a discrete random variable X, we denote its probability mass function by p(x) := P(X = x). If X is continuous, p(x) denotes its probability density function. Joint and conditional mass/density functions are denoted p(x, y) and p(y | x) respectively.
Entropy and related concepts. The entropy of a discrete random variable X is H(X) := E log 1 p(X) where here, as everywhere in this thesis, log :≡ log 2 denotes the binary logarithm. When X is continuous, the sum is replaced by an integral. .
The conditional entropy of Y given X is If X and Y are independent, then it is easy to show [6, Theorem 2.6.5] that The relative entropy distance from one probability function p(x) to another q(x) is The mutual information between X and Y is Hu correspondence A useful way to memorise the relationship between these concepts is the Hu correspondence. In the following picture, the area of each rectangle corresponds to the quantity.

H(Y) H(X)
The complex Gaussian distribution. A circularly-symmetric complex Gaussian random variable Z ∼ CN(0, σ 2 ) with variance σ 2 = E |Z| 2 is defined by the probability density function Maximum entropy. Out of all discrete random variables X on the set {0, 1, . . . , q − 1}, the maximum entropy is achieved when X is uniform [ Typical set. Let X be a random variable on a countable set X . Given a sequence X = (X [1], X [2], . . . , X[T]) ∈ X T of T random draws from X, then X will very likely take one of only 2 TH(X) ≤ |X | T different values, and each of these values is almost equally likely. These values make up the so-called typical set, and this property is called the asymptotic equipartition property.
We say (X, Y) is jointly typical of (X, Y) if X is in the typical set of X, Y is in the typical set of Y, and the pair (X, Y) is in the typical set of the pair (X, Y).

Channels, codes, and capacity
We will now set out mathematically the ideas of channels, codes, and capacity from Section 1.1.
To specify a channel, we need to say what inputs are allowed into the channel, what outputs can be produced, and how the noise randomly corrupts the input.
A common example of a channel is the binary symmetric channel. The BSC allows 'bits' -binary digits: 0s and 1s -into the channel. It then either outputs the same bit or, with some fixed probability, flips to the other bit. 2. a set Y, the output alphabet; 3. a probability transition function p(y | x) relating the two.
x Output alphabet Y y Definition 1.2. We can now formally define the binary symmetric channel with error probability p < 1 2 . This channel is defined by alphabets X = Y = {0, 1} and transition function A channel which is an accurate and widely-used model for wireless communication [5, Chapter 5.1] is the Gaussian channel. It arises from the sampling of a bandlimited continuous-time channel with white noise [7]. (For convenience, we assume a unit bandwidth.) Gaussian white noise is used for two reasons. First, it seems a reasonable model: the superposition of lots of small pieces of noise ought to (due to the central limit theorem) look roughly Gaussian. Second, it is the simplest case mathematically, and often leads to analytically tractable solutions.
The Gaussian channel takes any number as an input and corrupts it by adding random Gaussian noise. By convention, and for useful modelling reasons, the channel is usually defined in terms of complex numbers [5, Subsection 2.2.4]. Definition 1.3. The Gaussian channel with noise power σ 2 has alphabets X = Y = C, and probability transition density p(y | x) defined implicitly by the relationship Y = x + Z, where the Z ∼ CN(0, σ 2 ) are all independent.
(If the channel is used multiple times, we assume a new random Z is drawn each time.) x y Transition density of the Gaussian channel (real part only) Another channel we will examine in this thesis is the finite field channel. This channel can be a useful model of a Gaussian channel that has been quantised (or discretised). Definition 1.4. Let q be prime, and let Z be a random variable defined on the finite field F q = {0, 1, . . . , q − 1}. The finite field channel of size q with noise Z has alphabets X = Y = F q , and probability transition density p(y | x) defined implicitly by the relationship Y = x + Z (mod q). (Again, multiple uses assume independent Zs.) Note that the BSC is a special case of the finite field channel where q = 2 and Z = 1 with probability p or Z = 0 otherwise. Now that we have a channel, we can design codes for that channel. A code takes a set of M messages, and encodes each message into a string -called a codeword -of length T. After the channel has been used T times to send the codeword, there must be a rule for decoding the received string, to estimate which message was sent. The set of codewords {x(m) : m ∈ M} is called the codebook; the parameter T is called the block length.
The problem of channel coding works like this: • The transmitter (Alice) requires to send a message m ∈ M.
• Alice encodes this message into a codeword x(m) ∈ X T .
• Alice sends the first letter x(m) [1] of the codeword through the channel to the receiver (Bob). Bob receives a corrupted version y [1] ∈ Y of the letter, where the corruption has occurred at random according to p(y | x).
• Alice sends the second letter x(m) [2] of the codeword through the channel to Bob. Bob receives a corrupted version y [2] ∈ Y of the letter, where the corruption has occurred at random according to p(y | x).
• Alice sends the final letter x(m)[T] of the codeword through the channel to Bob. Bob receives a corrupted version y[T] ∈ Y of the letter, where the corruption has occurred at random according to p(y | x).
• Bob now decodes his received word y to make his estimate m(y) of Alice's original message m. Hopefully, m = m, and the message has been communicated successfully.
So the system as a whole looks like this (the channel is in grey): All channels considered in this thesis will be memoryless, in that the channel's current performance is independent of earlier behaviour. In other words, the transmission of codewords follows a product distribution So far, we have considered only static channels, where the probability transition function remains fixed over time. (Later, we will look at fast-fading channels, where the transition function is no longer fixed but changes from timeslot to timeslot.) Note that, from a mathematical point of view, what the messages are is unimportant -what matters is how many of them there are. So it often makes sense to choose the message set M to be something convenient. For example, when dealing with a finite field channel of size q, we often take M to be F S q , which has cardinality M = q S . In particular, when q = 2, the message set M = F S 2 = {0, 1} S is the set of all bit strings of length S = log 2 M. We define the rate of a code to be the number of bits that we can send per channel use. The number of bits is log 2 M, as above, and the number of channel uses is T, so the rate is (log 2 M)/T. Definition 1.6. The rate of an (M, T)-code is defined to be (log 2 M)/T bits per transmission.
(From now on, all logarithms are to base 2, and we just write log for log 2 .) Also associated with a code we have its error probability, the chance that a message is decoded incorrectly. (We take the average error probability across all messages, but if we were to use the maximum error probability, the main results of this chapter would be the same.) Definition 1.7. The average error probability is We can now give an example of a code for the BSC. Suppose there are two messages we might wish to send: "No" and "Yes", so M = {No, Yes}.
A very simple code could assign 0 to be the codeword for "No" and 1 to be the codeword for "Yes". This is a (2, 1)-code. It clearly has a rate of (log 2)/1 = 1 bit per transmission and error probability p.
To reduce the error probability, we will need a more sophisticated code. One method of coding would be the repetition code where each symbol is repeated T times, so x(No) = 00 · · · 0 ∈ X T x(Yes) = 11 · · · 1 ∈ X T . Definition 1.8. A (2, T)-code is called a T-repetition code if the codebook consists solely of the all-0 and all-1 codewords of length T.
The obvious method of decoding is the 'majority rule': if y has more 0s than 1s, decode as "No"; if y has more 1s than 0s, decode as "Yes". (If there are exactly T/2 of each, decoding may be performed arbitrarily.) Note that the rate of this code is (log 2)/T = 1/T, and the error probability is bounded by e ≥ p T , the probability that all T symbols flip.
What does it mean to be able to communicate through a channel at some desired rate r? Well, it means that there must exist a code for the channel with rate at least r and a low probability of error. How low? As low as we desire. If we want to limit the error probability to 5%, then there must be a code with rate at least r and error probability no more than 5%; but if we want the error probability to be as low as 1% or even 0.01%, there has to be a code for that too. Definition 1.9. Consider a channel (X , Y, p(y | x)).
A rate r is achievable if for any error tolerance > 0, there exists a code with rate at least r and error probability lower than .
Otherwise, r is not achievable, in that there exists an error threshold such that there exists no code with rate at least r and error probability lower than .
The capacity is defined to be the maximum achievable rate. Definition 1.10. Consider a channel (X , Y, p(y | x)). Then we define the capacity of the channel, c, to be the supremum of all achievable rates: c := sup{r : r is achievable}.
In other words, all rates r less than c are achievable, but no r above c is achievable.
Shannon calculated the capacity as the maximum mutual information between the input and output of a channel [4,Theorem 11].
The mutual information I(X : Y) between X and Y can be seen as a measure of 'how independent' X and Y are. If I(X : Y) is large, then X and Y are highly dependent, so knowledge of the output Y gives us lots of information about the input X; if I(X : Y) is small, then X and Y are highly independent, so knowledge of the output Y gives us little information about the input X. Theorem 1.11 (Shannon's channel coding theorem). Consider a discrete channel (X , Y, p(y | x)), that is, a channel where both X and Y are both countable sets.
Then the capacity c is given by the formula c = max X I(X : Y), where Y is related to X through p(y | x), and the maximum is over all input random variables X defined on X .
The characterisation of capacity given by Shannon's channel coding theorem (Theorem 1.11) allows us to calculate the capacity of the finite field channel and the BSC. The capacity of the BSC with error probability p is Capacity of the binary symmetric channel (We use the abbreviation D(Z) := log q − H(Z) since this is equal to the relative entropy distance D(p(z) p(u)) between Z and a uniform random variable U over F q .) Proof. Finite field channel. By Shannon's channel coding theorem (Theorem 1.11) we need to calculate the mutual information. This is This is maximised by choosing X to be uniform on F q , by (HB9), so that Y is uniform also, giving as required.
BSC. This result follows from recalling that the BSC is a special case of the finite field model.
Later in this thesis, we will often see examples of channels and networks whose capacities are a constant fraction of the finite field channel capacity. If a channel or network has capacity c = d D(Z) for some constant d, we say that the channel has d degrees of freedom (also known as the multiplexing gain or pre-log term). Definition 1.13. Given a discrete channel or network with capacity c, we define the degrees of freedom to be dof = c/D(Z) .
Clearly, the finite field channel itself has a single degree of freedom, that is we have dof = 1.
We have not yet talked about the proof of Shannon's channel coding theorem (Theorem 1.11).
To prove Shannon's channel coding theorem (and related theorems) we must prove two things: Achievability First, we must show that any rate below capacity r < c is achievable. That is, we must find a sequence of codes all with rates at least r < c, but with arbitrarily low error probabilities.
Converse Second, we must show that any rate above capacity r > c is not achievable. That is, we must show that for any sequence of codes all with rates at least r > c, the error probabilities must be bounded away from 0.
The converse part is proved using Fano's inequality [8], which bounds the error probability in terms of the conditional entropy across the channel H(Y | X) and the size of the message set M.
Shannon's key insight into the achievable part is the following: instead of trying carefully to design special codes with high rates and low error probabilities, we can instead just pick the code at random. That is, we choose the codeword letters X(m)[t] IID according to some distribution X. If we set M = 2 Tr , then the rate of the code will be at least r. We hope that by choosing T sufficiently large, the error probability will be driven arbitrarily low. (Later, we can optimise over the choice of X.) This random encoder can be twinned with an effective decoder to show that any rate r < c can be achieved. Two different decoders can be used: Joint typicality decoder The receiver takes the channel output y and finds the unique codeword x(m) such that the pair (x(m), y) is jointly typical of (X, Y (If the maximum isn't unique, we declare an error.) Shannon himself [4,Section 13] and most subsequent authors (for example [6,Chapter 7], [9, Chapter 10]) use the joint typicality approach, as it gives a fairly simple and short proof.
On the other hand, Gallager [10] used the maximum likelihood approach to prove Shannon's channel coding theorem, by bounding the error probability by e ≤ 2 −TE(r) , where E(r) is called the error exponent, and examining the error exponent for different values of r. We shall return to Gallager's maximum likelihood approach in Chapter 6, when proving a similar theorem for group testing.
We now outline the achievability proof using the joint typicality decoder. Basic facts about typical sets are given in the handbook (Section 1.2).
Sketch proof of achievability, Theorem 1.11. As above, we set the number of messages to be M = 2 Tr , choose codeword letters X(m)[t] IID at random according to some distribution X, and decode using a joint typicality decoder. There are two ways we could get an error.
First, the actual codeword X and the received output Y could fail to be jointly typical. But the theory of typical sets tell us that this event is very unlikely.
Second, another codeword X( m) could be jointly typical with Y, despite X( m) and Y actually being independent of each other. Since X( m) and Y are very likely to (marginally) typical, joint typicality occurs with approximate probability # jointly typical (x, y) by standard facts about typical sets (see the handbook, Section 1.2). Hence the probability of error is approximately So provided r < I(X : Y), then by choosing T large enough, the error probability can be made arbitrarily small. Choose X to maximise I(X : Y) to get the result.
In a sense, this theorem is quite a 'lucky' result: it turns out that the lower bound on capacity given by Shannon's random coding argument and the upper bound given by Fano's inequality coincide, to give us the equality c = max X I(X : Y).
For other networks, we may not be so lucky. However, similar proof strategies can be useful. If we can show that all rates below some r * are achievable, this gives us a lower bound on capacity: c ≥ r * . Conversely, if we can show that no rates above some r * are achievable, then we have an upper bound: c ≤ r * . In the point-to-point case, we have r * = r * = c. But even if there is a gap between the upper and lower bounds, the result can be useful in giving us an approximation to the capacity. In particular, sometimes there may be a limiting sense in which the upper and lower bounds are asymptotically equal -for example, as signal power or number of users tends to infinity.
It is often useful to think not just of individual codes, but of families of codes. One family of codes we have already seen is the repetition code (Definition 1.8).
MacKay [9,Section 11.4] divides families of codes into three separate categories, depending on how effective they are for their channel.

Bad codes
In bad families of codes, as we force the error probability to 0, the rate of the codes approaches 0 also.

Good codes
In good families of codes, as we force the error probability to 0, the rate of the codes is bounded above 0, but below capacity.

Very good codes
In very good families of codes, as we force the error probability to 0, the rate of the codes can be maintained arbitrarily close to capacity.
Earlier we saw that rate of the repetition code is 1/T, and its error probability is bounded by e > p T . Hence, to force the error probability e to 0, we must send T → ∞, and the rate tends to 0. Hence, the repetition code is a bad code. (MacKay notes, however, that bad codes are not necessarily practically useless [9, p. 183].) It is sufficient for this thesis to note that Shannon's channel coding theorem (Theorem 1.11) tells us that very good (capacity achieving) codes do exist, and that we can do much better than simple codes like the repetition code. (The design of good and very good practical codes is outside the scope of this thesis.) In later work in this thesis, rather than finding new codes from scratch, we will instead adapt these very good point-to-point channel codes for use in large networks.
A useful class of codes for finite field channels is the class of linear codes. If we take M = F S q for the message set again, then a linear code is a code whose encoding function x : F S q → F T q is a linear map. It's often useful to represent this linear map by an S × T matrix G, so x(m) = Gm. We call G the generator matrix of the code. The rate of such a code is (log M)/T = (S/T) log q. Definition 1.14. Consider a finite field channel of size q. Then a linear code is a (q S , T)-code with message set M = F S q and encoding function x(m) = Gm for some generator matrix G ∈ F S×T q . Any decoding function may be used.
We call S the rank of the code.
For example, the T-repetition code is a linear code with field size q = 2, rank S = 1 and 1 × T generator matrix G = (1 1 · · · 1).
The important fact about linear codes (at least for finite field channels) is that, when paired with an optimal decoder, very good (capacity achieving) linear codes exist [9,Chapter 14]. Thus, if we restrict our attention only to linear codes, we can still achieve all rates up to the capacity c = D(Z) of the finite field channel. Theorem 1.15. Very good linear codes exist for all finite field channels with nonzero capacity.
The current state of the art for high-rate practical codes -that is codes with low encoding and decoding complexity and moderate block lengths -is a class of random linear codes called low-density parity-check codes [9,Chapter 47]. (See the textbook of Richardson and Urbanke [11] for more details.)

Power
We have not yet looked at codes for the Gaussian channel.
The capacity of the Gaussian channel is infinite, as there exist codes with arbitrarily high rates and simultaneously arbitrarily low error probabilities.
To see this, consider the following. Let M = {1, 2, . . . , M}, encode using x(m) = mN for some very large N, and decode to the nearest positive integer to y/N (which should be roughly m). This is an (M, 1)-code, with rate log M. By picking N large enough, the error probability can be made arbitrarily small; but by picking M large enough, the rate can be made arbitrarily high. This is neither mathematically interesting nor physically realistic. Antennas for wireless networks are not capable of transmitting at arbitrarily high powers. Thus, we introduce a power constraint: that for all codewords x, the power -the mean square value -is limited by a prescribed value P.
The power of a code is defined to be the maximum power of any codeword.
So we want to limit our attention to codes whose power is at most the power constraint P.
A rate r is achievable with power P if for any error tolerance > 0, there exists a code of power at most P with rate at least r and error probability lower than .
Otherwise, r is not achievable with power P, in that there exists an error threshold such that there exists no code of power at most P with rate at least r and error probability lower than . Definition 1.18. Consider a channel (X , Y, p(y | x)). Then we define the capacity of the channel with power P to be the supremum of all achievable rates: c := sup{r : r is achievable with power P}.
In other words, all rates r less than c are achievable with power P, but no r above c is achievable.
Shannon calculated the capacity of the Gaussian channel with a power constraint in his original paper [4,Theorem 17] Theorem 1.19. Consider the Gaussian channel with power constraint P and noise power σ 2 .
Then the capacity is given by the formula c = log (1 + snr), where we have defined the signal-to-noise ratio snr := P/σ 2 to be the ratio of the signal power to the noise power So at low snr, capacity grows linearly with snr; whereas at high snr, capacity only grows logarithmically.
Later in this thesis, we will often see examples of channels and networks whose capacities at high-snr are often a constant fraction of the Gaussian channel capacity c ≈ log snr. If a channel or network has capacity c = d log snr + o(log snr) at snr → ∞ for some constant d, we say that the channel has d degrees of freedom. (This is the Gaussian analogy to the finite field degrees of freedom in Defintion 1.13.) Definition 1.20. Given a channel with capacity c(snr) and power constraint P = snr σ 2 , we define the degrees of freedom to be dof = lim snr→∞ c(snr) log snr where this limit exists.
From (1.1) the Gaussian channel itself has a single degree of freedom, that is, we have dof = 1.
Sketch proof of Theorem 1. 19. In a similar manner to Shannon's channel coding theorem (Theorem 1.11), it can be shown that the capacity of the Gaussian channel with a power constraint is max X:E |X| 2 ≤P I(X : Y). (This is certainly a believable result: it is the same formula as for discrete channels, with the additional constraint that the expected power satisfies the constraint.) It remains to calculate the mutual information. This is Note that Hence the entropy of Y is maximised by choosing X to be complex Gaussian with variance P, by (HB10), so that Y is Gaussian also, with power P + σ 2 , giving c := max as required.
Note that the input distribution that achieves capacity is X ∼ CN(0, P). So the signal is statistically the same -that is, distributed in the same parametric family -as noise, but with a different power. This fact will be useful later.
As we mentioned earlier, Theorem 1.19 tells us that very good (capacity achieving) codes exist for the Gaussian channel. Later, we will adapt these very good point-to-point codes for use in large Gaussian networks.

Fading
In their standard forms, the finite field and Gaussian channels are represented by the formula . We can interpret this as the signal being transmitted perfectly through the channel, except for the addition of some noise. However, for a more realistic model of wireless networks, we need to account for the way the signal itself transforms as it is sent through the channel. For example, in the Gaussian channel, we might expect the signal power to decay over long distances, and standard physical models suggest that the phase of the signal arg x[t] will alter as it is transmitted through space [5, Section 2.1].
We can model these concepts by introducing a fading (or channel state) coefficient H[t]. Our channels now become We are interested in three cases: Before we continue, we have a useful simplification to make. Since the fading Gaussian channel will be used a lot in this thesis, it makes sense to change our units, so that the noise power and power constraint are both unity. To that end, set Under this change of units we have, after dividing through by σ, From now on, we will solely use this model, so will shall drop the tildes. Note that under this change of units, the signal-to-noise ratio 1| H| 2 1 remains the same. (Note also that under this change, the Gaussian channel with no fading inherits a fixed fading coefficient

Fixed fading
Fixed fading models fading that is constant and predictable, such as the decay in signal power between a non-moving transmitter and a non-moving receiver within a fixed environment.
We model the fading coefficient as a deterministic constant fixed for all time, How does the capacity alter now? For the finite field channel we have h ∈ F q . Note that for nonzero h, the function x → hx is a bijection, so the channel is equivalent to that without fading (h = 1), and still has capacity D(Z), from Theorem 1.12. On the other hand, if h = 0, then Y is always 0, and all signals are indistinguishable, so the capacity is 0. Hence, for the finite field channel, the capacity is (For simplicity, we often just assume that h is nonzero, so the capacity is unchanged as c = D(Z).) For the Gaussian channel with power constraint P = 1 we have h ∈ C. The power constraint is now |hx| 2 = |h| 2 |x| 2 ≤ |h| 2 . So this channel is equivalent to one with no fading, but with the power constraint changed from 1 to |h| 2 . The capacity is thus with the new convention that snr denotes the signal-to-noise ratio at the receiver: snr = |h| 2 P/σ 2 = |h| 2 .
To summarize: For modelling wireless networks, we will often use a Gaussian channel with fixed fading coefficient h that decays like a power law over distance. That is, we have h = kρ −α/2 , where ρ > 0 is the distance between a transmitter and receiver and k > 0 is a constant.
The parameter α > 0 -called the attenuation -represents how resistive the environment is to the transmission of radio waves. (Some authors call α/2 the attenuation; we do not.) Low α represents an environment with few obstacles to signals; high α implies that a lot of the signal power is absorbed before reaching the receiver. In free space, standard physical considerations imply that α = 2 or 3; for built-up areas, values of α of roughly 4 or 5 seem more appropriate [5, Section 2.1]. The capacity of such a channel is c = log(1 + k 2 ρ −α ), by Theorem 1.21.
(Power-law attenuation fails to be realistic for small distances ρ 1. Here the received power would be greater than the transmitted power, which violates the conservation of energy. Some authors therefore prefer alternative models such as h = min{1, kρ −α/2 } or h = k(ρ + ρ 0 ) −α/2 for some fixed constant ρ 0 .) We could also include a fixed phase change in this model by setting h = kρ −α/2 e iθ . In free space, the phase would scale linearly with distance, so h = kρ −α/2 e 2πiρ/λ , where λ is the carrier wavelength [12]. Note that we still have |h| 2 = k 2 ρ −α , so the capacity is the same.

Fast fading
Fast fading models a situation where the state of the channel is changing rapidly, such as a commuter using a mobile phone on a train. We model this as H[t] being random according to some distribution H but renewing at each channel use; that is, the H[t] are independent and identically distributed like H.
When we deal with fast fading, the performance of a channel will depend on whether the transmitter and receiver know the current value of H[t], or just the general distribution H, and whether the transmitter can use this knowledge to vary their power.
Throughout this thesis, we assume that both the transmitter and the receiver know H[t]. This is known as having perfect channel state information at the transmitter (CSIT) and at the receiver (CSIR). We presume that this knowledge is causal, that is, the receiver and transmitter learn H[t] immediately prior to the transmission of x[t] and reception of y[t] respectively. In other words, they have no prediction of the channel future to use (except, of course, knowing the future channel states will be IID according to H).
When the transmitter has CSIT in a Gaussian channel, we must specify whether or not she can use this information to operate at varying power. So there are two different types of power constraint. Let x[t](h) be the tth codeword letter chosen in channel state h, and let H be the support of H. (Recall from our simplification (1.2) that we now have P = 1.) Universal A universal power constraint demands that the power constraint is held universally over each channel state realisation. That is, we demand Average An average power demands that the power constraint is held when averaged over all channel state realisations. That is, we demand (The second term assumes H is discrete; the summation can be replaced by an integral if H is continuous.) An average power constraint allows a transmitter to use extra power when the channel is at its strongest, and save power when the channel is weak. (For more details, see the textbook of Tse and Viswanath [5,Subsection 5.3.3].) In this thesis, we always assume a universal power constraint. First, it is mathematically simpler to deal with. Second, it is physically unrealistic for transmitters to operate above their average power for long periods of time.
(Similarly, in a frequency-selective channel, one must specify whether the the power constraint is enforced in each individual subchannel, or an average across all frequencies.) So, assuming perfect CSIT and CSIR (with a universal power constraint in the Gaussian case) we have the following. Then the fast fading capacity is equal to the average fixed fading capacity, in that c = Ec(H).
In the most general case, this theorem is due to Goldsmith and Varaiya [13]. We sketch the achievability proof for the case when H is discrete. ( But by the strong law of large numbers, we have the ergodicity property that lim T→∞ π(h, T) = P (H = h) (almost surely). Hence (again almost surely), The converse can be proved using Fano's inequality, as with Shannon's channel coding theorem (Theorem 1.11).
The result for continuous H can be derived from this using a quantisation argument [13,Appendix].
Since this result relies on the sequence of fading parameters being ergodic, c is sometimes called the ergodic capacity. So the above result can be interpreted as 'the ergodic capacity is the average capacity.' (Later, we will see how using interference alignment in networks can allow us to achieve an ergodic capacity that is higher than the average capacity.) Applying Theorem 1.22 to the finite field channel (Theorem 1.12), we get (Again, we often assume H is never 0, so c = D(Z) still.) For the Gaussian channel (Theorem 1.19), we have (Since SNR is random here, we capitalise it.) One type of fast fading for the Gaussian channel could be a rapidly changing phase, This is a good model of wireless communication when there are many paths a signal could take from transmitter to receiver (in a built-up area, for example) [

Slow fading
Slow fading models the situation where the state of a channel is varying, but is doing so very slowly, or where the channel state can only be modelled as random, but remains fixed. Here we take H[t] = H as initially random, but remaining fixed for all times t = 1, 2, . . . , T.
Since the channel state is random, so is the capacity C = c(H): if the fading is particularly deep, H ≈ 0, then the capacity is likely to be very low; if the fading is lighter, then the capacity will be higher. Specifically, under the event that H = h we have C = c(h).
(As with H, when the capacity is a random variable, we capitalise it as C.) One way to summarise the random variable C would be through its cumulative distribution function p out (r) := P(C ≤ r) = P(c(H) ≤ r), known as the outage probability. We can interpret this as the following: if we are trying to communicate at some fixed rate r, then then p out (r) is the probability that we are unable to do so -we say the channel is in outage. Definition 1.23. For a slow fading channel with (random) capacity C, the outage probability p out : The event {C ≤ r} is called outage.
For the Gaussian channel, we have (following Theorem 1.19 and recalling that log denotes log 2 ) where SNR = |H| 2 is the signal-to-noise ratio.
For the finite field channel, we have (following Theorem 1.12) In wireless networks, a good model is to position nodes at random and use distance-based attenuation fading. Since distances between nodes are random, the fading is random too. But once the nodes are positioned, the distances remain fixed. Hence, this gives a form of slow fading.

Notes
The section consists of a review of the existing literature; the mathematical content is not claimed to be new.
The basic concepts of information theory as outlined in this chapter are all due to Shannon's original paper [4]. An exception is the concept of relative entropy distance, due to Kullback and Leibler [15]; and the Hu correspondence, due to Hu [16].
Although Shannon [4, Theorem 11] first came up with the channel coding theorem (Theorem 1.11), he provided only a sketch proof; the sketch proof provided here is along the lines of the rigorous proof by Cover [17]. The maximum likelihood approach is due to Gallager [10].

Interference
In this chapter, we will look at ways of dealing with interference in communications networks.
To start with, we will define information theoretic networks, in a similar manner to our definition of channels in Chapter 1.
We will then look at methods of combating interference -the unwanted signals from other transmitters that a receiver is not interested in.
For the purpose of definiteness, we will consider these in the context of the interference networks and (mostly) the fading Gaussian case. However, the techniques are useful in wider contexts.
We look at some simple schemes -interference as noise, decode and subtract, and resource division -and then look at a family of new schemes known as interference alignment. We pay particular attention to a scheme called ergodic interference alignment, which we will use later in Chapters 4 and 5.

Wired and wireless networks
In this chapter, we will outline the theory of networks. We will concentrate on accurate models of real-world wireless networks.
Wireless communications are becoming increasingly ubiquitous. From older technologies like radios, to cutting-edge innovations such as WiFi, Bluetooth and ZigBee, the convenience of the untethered nature of wireless is popular on both large and small scales for businesses and consumers alike.
Compared to a wired (or wireline) network, wireless networks provide much greater challenge to engineers and technicians. The main problems are: Broadcast Each receiver can send only one signal, regardless of how many messages they are trying to send to how many people.
Interference Receivers receive not just the signal corresponding to messages intended for them, but also all of the other transmitted signals as well. These signals are called interference.

Superposition
Receivers cannot tell which signal corresponds to which message, but rather receive the superposition (that is, the sum) of all such signals. In this thesis, we will mainly be looking at networks where each transmitter wishes to send a single message to a single receiver, and each receiver requires a single message from a single transmitter. Thus, the broadcast and superposition problems are less important that that of interference.

Wired networks Wireless networks
We capture this problem mathematically by modelling the network by a probability transition function p(y 1 , . . . , y n | x 1 , . . . x n ) relating all transmitted signals to all received signals.

Wired network Wireless network
Later in this chapter, we consider a number of methods for dealing with such interference.

Networks
Point-to-point links, as we discussed in the previous chapter, are fairly well understood. Networks, however, are much trickier.
By a network, we mean a number of transmitters and receivers, all trying to send and receive messages through the same medium. 3. a probability transition function p (y j : j ∈ R) | (x i : i ∈ T ) relating them.
(In general, an agent is allowed to be a duplex operator, that is to be both a transmitter and a receiver, which can act as a relay in a network. However, duplex operation will not be used in this thesis, so our definition precludes this.) Again, we will be interested in the Gaussian and finite field channels with fading. Because there are now many transmitters and receivers, we will let H ji [t] denote the fading coefficient at receiver j from transmitter i.
The Gaussian and finite-field networks work in much the same way as the point-to-point channels, with the change that now receivers experience the superposition (that is, sum) of all signals sent.
The finite field network of size q with noise Z has X i = Y j = F q for all i and j. The probability transition measure is implied by the relationship where Z j [t] are independently and identically distributed like Z.
When it's convenient, we will write these networks in matrix form, that is where To design a code for a network, we need to specify which transmitters are trying to send a message to which receivers; then each transmitter needs an encoding function, and each receiver a decoding function (or more than one, if they are receiving many messages).

Definition 2.3. A code for the network
2. a message set M ij of cardinality M ij for each link i→j ∈ L; 3. an encoding function On link i→j ∈ L, the rate is r ij := log M ij /T, the rate vector is r = (r ij : i→ j ∈ L), and the sum-rate is r Σ := ∑ i→j∈L r ij . The error probability on link i→j is When dealing with the Gaussian case, the power of transmitter i is the maximum value of |x i | 2 : Some common examples of networks are the following: The point-to-point link is just a special case of a network with

Alice Bob
The multiple-access network has multiple transmitters sending to one receiver, so  The interference network consists of multiple point-to-point links communicating over the same medium, so (Note that this differs from n independent point-to-point links, since each receiver is also receiving the signals from the other transmitters, even though they have no use for that signal.)  As with point-to-point links, we are interested in the maximum rate at which we can send information through a network. However, since we now have several competing links in the same network, no one benchmark will describe this. For example, achieving a high rate on one particular link may use up a lot of channel resources, leading to slower communication on another link. (Consider trying to hold a conversation in a room where lots of other people are shouting.) Instead the set of achievable rate vectors will be a region of L-space; we call this the capacity region. (Recall from Definition 2.3 that L = |L| is the number of links in the network.) A rate vector r = (r ij : i→ j ∈ L) is achievable for links L if for any error tolerance > 0, there exists a code for L with rate on each link i→j at least r ij and all error probabilities lower than .
Otherwise, r is not achievable, in that there exists an error threshold such that there exists no code for L with rates at least r ij and all error probabilities lower than .
Then we define the capacity region of the channel, C, to be the closure of the set of all achievable vectors: In other words, all rate vectors r in the interior of C are achievable, but no r outside c is achievable.
Note that the capacity region will always be convex: Suppose the rate vectors r 1 and r 2 are both achievable. Then the rate vector λr 1 + (1 − λ)r 2 , for λ ∈ [0, 1] is achievable by operating at r 1 for λT of the time points and at r 2 for the remaining (1 − λ)T timeslots. This strategy is known as time sharing; we discuss this further in Subsection 2.4.1.

Definition 2.7.
We define the sum-capacity c Σ to be the maximum achievable sum-rate, so c Σ := max r∈C r Σ = sup{r Σ : r is achievable}.
The current knowledge of capacity regions for these networks in the Gaussian and general cases is summarised in the table below.

Network General case Gaussian case
Point-to-point known (Theorem 1.11) known (Theorem 1.19) Multiple-access known [21,22] known (Theorem 2.8) Broadcast unknown; known for some special cases [23] known [24] Interference unknown; known for some special cases [25] unknown; known for some special cases [25]; sum-capacity known for most two-user cases [26] X unknown unknown Later, we will use the capacity region of the multiple-access network. It was discovered independently by Ahlswede [21] and Liao [22] in the 1970s. In the Gaussian case, it simplifies to the following: Theorem 2.8. The capacity region of the multiple-access network of n transmitters with fixed fading is the set of (r 1 , r 2 , . . . , r n ) ∈ R n + satisfying ∑ i∈S r i ≤ log 1 + ∑ i∈S snr i for all S ⊆ {1, 2, . . . , n}, where snr i := |h i | 2 is the signal-to-noise ratio from transmitter i. The sum-capacity is In this thesis, we will mostly be interested in the n-user interference network. We will use the word 'user' to denote a matching transmitter-receiver pair. Hence, an n-user network consists of n transmitters and n receivers. We will mostly be interested in the large n limit.
Recent work by Jafar [27] in the fixed snr, n → ∞ regime has shown much promise. We review Jafar's work in detail later in this chapter and in Chapter 4, and extend it to physical models of wireless networks.
Alternatively, in the fixed n, snr → ∞ regime, Cadambe and Jafar [28] used interference alignment to deduce the limiting behaviour within o(log(snr)). These techniques were extended by the same authors [29] to more general models in the presence of feedback and other effects.
For small n, the classical bounds due to Han and Kobayashi [30] as refined by Chong, Montani, Garg and El Gamel [31] for the two-user Gaussian interference network have recently been extended. For example Etkin, Tse, and Wang [32] have produced a characterization of capacity accurate to within one bit. These results were extended by Bresler, Parekh, and Tse [33], using insights based on a deterministic channel which approximates the Gaussian channel with sufficient accuracy, to prove results for many-to-one and one-tomany Gaussian interference channels.
A different approach towards finding the capacity of large communications networks is given by the deterministic approach of Avestimehr, Diggavi, and Tse [34]. They show how capacities can be calculated up to a gap determined by the number of users n, across all values of snr.
More generally, in problems concerning networks with a large number of nodes, the work of Gupta and Kumar [35] uses techniques based on Voronoi tesselations to establish scaling laws. (See also the survey paper of Xue and Kumar [36] for a review of the information theoretical techniques that can be applied to this problem.) Ozgür, Lévêque, and Tse [37] andÖzgür and Lévêque [38] use a similar model of dense random network placements, though using the same points as both transmitters and receivers. They describe a hierarchical scheme, where nodes are successively assembled into groups of increasing size, each group collectively acting as a multiple antenna transmitter or receiver, and restrict to transmissions at a common rate. They show [37, Theorems 3.1, 3.2] that for any > 0 there exists a constant k = k( ) depending on and a fixed constant K such that (2.1) These bounds are close to stating that c Σ grows like n, but without the explicit constant that Jafar [27] and the work in Chapter 4 of this thesis achieve. (Later, we produce a version of the upper bound (2.1) without the logarithmic factor and being explicit about the constant K. Note that this result is proved under a model that differs from that ofÖzgür, Lévêque, and Tse [37], and the fact that we have a total of 2n nodes rather than n -although this is unimportant for asymptotic results. Further, in their work, local collaboration and relaying are both allowed, meaning that the true rate in their scenario could indeed be n log n .)

Interference as noise
Recall that we mentioned in Section 1.4 that the optimal input distribution to the Gaussian channel is CN(0, P), while the noise is CN(0, σ 2 ). Thus, interference has the same distribution as noise (after an appropriate scaling). So to receiver j, the received signal In other words, treating interference as noise allows user j to communicate at rate Here, |h jj | 2 is the received power of the signal, and ∑ i =j |h ji | 2 the received power of the interfering signals from other transmitters. We call the signal-to-interference-plus-noise ratio at receiver j. Theorem 2.9. Consider an n-user Gaussian interference network. The rates r j = log(1 + sinr j ) are simultaneously achievable.
The convex hull of the set of r with r j ≤ log(1 + sinr j ) for all j is an inner bound for the capacity region.
When the interference is weak, that is when ∑ i =j |h ji | 2 1, this strategy will be quite effective, as we will have Hence, in this situation, user j can communicate at almost the same rate it could were there no interference at all.
However, if the interference is strong, this strategy will lead to a dramatic decrease in the rate. In this case we will need different strategies.

Decode and subtract
The tactic of treating interference as noise suggests a method of dealing with strong interference.
Suppose we have just one interfering link 2→1 that is very strong. Then we can treat the interference as signal, and treat the signal itself as noise. This allows us to decode the interfering signal x 2 (with x 1 as noise). Once we have decoded x 2 , we know the interference h 12 x 2 (since we have perfect channel state information), allowing us to subtract it. This forms the interference free signal In this case, receiver 1 requires to decode the interference, and then r 1 ≤ log(1 + snr 1 ) to decode the signal, once the interference has been subtracted.
If the 'interference-to-noise-plus-signal ratio' |h 12 | 2 /(|h 11 | 2 + 1) is largethat is, if the interference |h 12 | 2 is strong compared to the signal |h 11 | 2 -then this will be almost as effective as if no noise were present.

The problem of mid-level interference
So far, we have two principles: Weak interference should be treated as noise.
Strong interference should first be decoded, and then subtracted.
This leads to a natural question: what about mid-level interference? That is, what is the best way of dealing with interference when the power of the interference is roughly equal to the power of the signal?
Indeed, there are many plausible real-life situations where the mid-level interference would seem to be the most likely.
For example, in cellular networks (such as mobile phone networks), we have a phenomenon known as the edge-of-cell effect. This describes the phenomenon that near the edge of a cell, the strength of a signal is of a very similar level to if it just fell out of the cell. Combating the mid-level interference of these edge-of-cell transmitters is essential to maintaining a high-quality system.
For users near the centre of cells, the signal is much stronger than the interference.
For users near the edge of cells, the signal and interference are of similar strengths.
In fact, dealing with this mid-level interference turns out to be particularly important in multi-user networks; while weak and strong interference are easily dealt with, even rare occurrences of mid-level interference can severely restrict the performance of such a network. The following example, due to Jafar [27], illustrates this.
Consider a two-user Gaussian interference network, as governed by the input-output equations We will use a model with a fast-fading phase. So where the Θ ji [t] are IID uniform on [0, 2π).
Here inr ji = |h ji | 2 is the interference-to-noise ratio at receiver j from transmitter i.
For simplicity, we shall fix the direct links to be of equal strength: snr 1 = snr 2 =: snr.
Now suppose just one of the two interfering crosslinks is precisely this mid-level interference: so inr 21 = snr too. "Regardless of the value of inr 12 "! This is worth emphasising: just one crosslink of this mid-level interference has completely determined the sumcapacity of the whole network.
In Chapter 4, we shall see similar phenomena for networks with many more users, where the study of bottleneck links will be vitally important.
Proof. Direct part. Achievability follows from using ergodic interference alignment (Theorem 2.14), which we consider later in Section 2.6, or by timesharing (Section 2.6.1).
Converse part. Suppose we have a code allowing us to achieve the sum-rate Suppose a genie provides receiver 2 with transmitter 1's message (which could only increase the capacity of the network). This allows receiver 2 to cancel the interference due to x 1 .
By assumption, receiver 1 can decode his own message, and thus cancel the intended signal x 1 from his received signal y 1 .
This leaves the two receivers with statistically equivalent signals. Therefore, if receiver 2 can decode message m 2 -which it can by assumption -then so can receiver 1.
Since receiver 1 is able to decode both messages, the sum rate cannot be more than the sum rate capacity of the multiple access channel seen at receiver 1, which by Theorem 2.8 is r Σ ≤ log(1 + 2snr).
(We will use a similar proof strategy later to prove Lemma 4.11.) This shows that dealing well with this mid-level interference will be particularly important. We examine ways of doing so in the next section.

Resource division
When faced with mid-level interference, a simple way of dealing with it is to share out the channel resources between the transmitters, to stop the interference from getting in the way. (This technique is often known as orthogonalisation.) This idea is best illustrated by examples, of which we give three below. A big advantage of resource-division strategies is that they are fairly easy to set up, and require neither detailed ongoing channel knowledge nor high computational complexity. There is also little need for cooperation between users after setup.
In this section, we assume for simplicity that all snrs are equal.

. . . by time
In schemes which share out the time resource, each transmitter is given sole use of the channel for some period of time, in return for which they may not transmit the rest of the time.
Consider the case of the finite-field model. At any particular time, only one user has control of the channel, and they can communicate up to their singleuser capacity D(Z). All the other transmitters are silent, so the sum-rate is also r Σ = D(Z).
Each user can communicate at a rate r = D(Z)/n, for dof = 1/n degrees of freedom each (recall Definition 1.13), which in particular tends to 0 as the number of users n gets large. Naturally this is undesirable.
For the Gaussian model, transmitters can take advantage of the fact that they will only be transmitting part of the day, yet are operating under an average power constraint. Hence, when they are transmitting, transmitters can use power nP instead. Hence, each user can communicate at a rate r = 1 n log(1 + nsnr).
Note that for low snr we have which is the same as if there was no interference at all. Hence, for low snr, these schemes are optimal. For high snr (the more common case), we have a reduction over the single-user case of a factor of 1/n again. That is, each user has dof = 1/n degrees of freedom each, for a total of dof Σ = 1 degrees of freedom all together (recall Definition 1.20).
In summary: Theorem 2.11. Consider an n-user finite field interference network. Then the rates r i = D(Z)/n are simultaneously achievable, for a sum-rate of r Σ = D(Z) and dof Σ = 1.
Consider an n-user Gaussian interference network. Then the rates r i = 1 n log(1 + nsnr i ) are simultaneously achievable. If all snrs are equal, this has a sum-rate of r Σ = log(1 + nsnr), which has dof Σ = 1.
Høst-Madsen and Nosratinia showed that dof = 1/2 each, for a total of dof Σ = 1 is optimal for n = 2 users, and, more generally, showed that [39, They further conjectured that in fact it is the lower bound that is tight, and that dof Σ = 1 is optimal [39, Section IV]. In other words, they conjectured that resource division strategies were also optimal at high snr. We will later see that this is not the case.
Note that this scheme, as with all resource division schemes, requires a small amount of precoordination between users, to decide which user is alloted which timeslot. We do not consider in this thesis the problem of how to conduct this cooperation.

. . . by frequency
In schemes that share out the the frequency resource, each user is alloted a section of the frequency spectrum along which they may transmit, while remaining quiet over all other bandwidths.
This leads again to an average per-user capacity of c/n again. Second-generation (GSM) mobile phone networks use a mixture of resource division by time and by frequency to share a channel of bandwidth 25 MHz between up to 1000 transmitters. First the spectrum is shared, giving 125 channels of bandwidth 200 kHz each. Then within each of these subchannels, the time is divided between up to 8 transmitters in time slots of 577 µs at a time [

. . . by codeword space
Code division multiple access (CDMA) is another way of allowing multiple users to use a shared channel. It works as follows. (For the purpose of simplifying this example, we shall think of a noiseless binary channel.) Assume each transmitter i wishes to send a symbol x i ∈ {0, 1}. Using CDMA it does this over T channel uses. Each transmitter i is given a vector v i ∈ {0, 1} T . If that transmitter wish to send x i = 1, she instead transmits the vector v i over T channel uses; if she wishes to send x i = 0, she instead transmits 0, the zero vector of length T. In other words, transmitter i sends The receivers then receive the superposition y = ∑ n i=1 x i v i . If the vectors were linearly independent (for which T ≥ n is necessary but not sufficient), then each x i can be recovered.
Schemes such as this can be thought of as sharing the dimensions of the codeword space {0, 1} T among the n users, and so is another form of resource division.

Interference alignment
Interference alignment is the name for a new class of schemes for dealing with interference based on the following idea: if transmitters plan their signalling correctly, interference can 'align' at each receiver, with the desired signal split off separately. This allows receivers to share their resources just two wayshalf for the signal, and half for all the 'aligned' interference. Thus all users can communicate at (roughly) the rate they could if there were just one interfering link.
In particular, this means that each user can obtain 1/2 a degree of freedom, leading to dof = n/2 degrees of freedom overall. So in fact, the upper bound (2.2) of Høst-Madsen and Nosratinia [39, Section IV] turns out to be correct, disproving their conjecture that the lower bound dof = 1 was tight. (The conjecture was formally settled in the negative by Cadambe, Jafar, and Wang [41].) Like resource division, interference alignment can be performed in a number of different ways. We show these by three toy examples, before concentrating on the specific case that will be useful to us later.
These schemes require channel state information at the transmitter (CSIT), in that the signal set in any time slot depends on the channel state coefficients at that time.

. . . by codeword space
Note that CDMA (see Section 2.6.3) was, in some sense, wasteful for the interference network, since it allowed every receiver to decode every message, as if it were an X network. Whereas in fact, we only required each receiver to decode its own message.
Interference alignment by codeword choice, due to Cadambe and Jafar [28], develops this idea further. Each receiver receives a superposition of all the transmitters' (faded) signals, but by 'aligning' the interference, the receiver can work out its own signal, at less of a sacrifice than CDMA.
Consider the following 3-user fading interference network: Note for this toy example we have chosen the unusual channel state matrix which has diagonal entries (corresponding to direct links) all equal to 1, and off-diagonal entries (interfering links) all equal to i. Suppose now that transmitters send their signal as just real numbers (taking advantage of the power constraint to send at twice the power). The receivers will receive their desired signal in the real subspace, but the interference will be aligned in the (purely) imaginary subspace.
Thus, each user can communicate interference-free at rate r i = 1 2 log(1 + 2snr). Since we saw earlier that this was optimal at high snr for 2 users, it must certainly be optimal for 3 users too. Hence, this interference network has a sum-capacity of better than the r Σ = log(1 + 3snr) achievable by resource division. Cadambe and Jafar [28] managed to develop this idea, to show that it was possible for any values of fading parameters (provided there are no 'unexpected' linear dependencies -this would be avoided almost surely if the fading coefficient were from continuous distributions, for example).
They showed how transmitters can construct their signals so that at each receiver the signal is contained in one subspace of the signal space, and all the interference in another disjoint subspace, with both subspaces using roughly half of the available dimensions.
Specifically, they showed the following [28, Theorem 1]. (Recall the definition of degrees of freedom from Definition 1.20.) Theorem 2.12. Consider a Gaussian interference network with fixed fading coefficients h ji . Then the total number of degrees of freedom is dof Σ = n/2.
That is, for equal snrs, the sum-capacity is Note that the per-user capacity is compared with a single-user rate of so the rate has been roughly halved. This compares well to the reduction to 1/n of resource division strategies, at least when n > 2. El Ayach, Peters, and Heath [42] have conducted experiments that show that this interference alignment technique can perform well in real life for n = 3 users, with performance close to that predicted by theory.

. . . by time
If a network has time delays, we can take advantage of these delays to align interference in the time domain. Interference alignment by time was first considered by Grokop, Tse and Yates [43]. However, due to the computational complexity of such schemes and the lack of physical applicability, it has received little attention since.
Specifically let τ ji be the time delay between transmitter i and receiver j.
Thus we have the model Consider a toy example with the following time delays: Note that this has been set up so that delays on direct links are odd numbers, while delays on crosslinks are even numbers.
This allows us to use the following strategy. Transmitters only send symbols at the odd numbered times, t = 1, 3, 5, . . . . Then at even-numbered times, receivers will only get their desired signal (since odd + odd = even), and at odd-numbered times, two lots of 'aligned' interference (odd + even = odd).
Hence, users can communicate at half their single-user rate.
Grokop, Tse, and Yates showed a generalisation of this, but it is quite complicated: see their paper [43, Theorem 3.1] for details.

. . . by channel state
Consider a fast fading 3-user interference network where the channel state matrix can take either of the following two values Note that that this toy example has been set up such that H + H = I (mod 2).
Nazer, Gastpar, Jafar, and Viswanath [44] discovered a method of interference alignment that can code across the two channel states to recover a single message. Transmitters send the same signal in both states, and receivers combine two estimates to recover the desired message.
Nazer and coauthors named this scheme ergodic interference alignment. We investigate this further in the next section.

. . . over the rational numbers
Interference alignment by codeword space and by channel state both require a channel which changes over time (or, equivalent, across the frequency spectrum), while interference alignment by time requires the existence of time delays. For some time, this left open the question of whether a form of interference alignment could be performed over a static channel without delays.
The question was answered in the positive Motahari, Gharan, Maddah-Ali, and Khandani, with a scheme they call real interference alignment [45].
The strategy works by effectively 'vectorising' the channel. Specifically, we can treat the real numbers R as a vector space over the rational numbers Q. Then we can treat a real signal x ∈ R as a vector x = ∑ k λ k v k , where λ k ∈ Q and the v k ∈ R are some basis real numbers.
Using theorems about Diophantine rational approximations to real numbers, Motahari and coauthors deduce that real interference alignment achieves n/2 total degrees of freedom for the Gaussian interference channel.
Interested readers are referred to the original paper for further details [45].

Ergodic interference alignment
It's easiest to analyse ergodic interference alignment by first looking at the finite field channel. For convenience, we will assume that the fast-fading coefficients are IID uniform on F q \ {0}.
Recall from Theorem 1.12 that the single-user capacity of the finite field channel with non-zero fading is D(Z) := log q − H(Z).
The main lemma that gets ergodic interference alignment to work is the following [46, Theorem 1 and Corollary 2]. It is based on this observation: although receiver j would normally wish to reconstruct just its own message m j , it is, in fact, easier to reconstruct the 'pseudomessage' m j := ∑ n i=1 H ji m i . Lemma 2.13. Let M = F S q . Consider the finite field interference network. Then each receiver j can decode the linear combination of messages m j = ∑ n i=1 H ji m i at rate D(Z).
Proof. The key here is for all transmitters to use the same linear code. Let the generator matrix of this code be G . Write g[t] for the tth row of G, so x i [t] = g[t]m i (since m i is a column vector). Then each receiver j sees signal But this is precisely as if the single message m i was sent with the linear code. Since very good linear codes exist (Theorem 1.15), this can be done at rates up to the single-user capacity c = D(Z).
The technique proceeds as follows: Match a state H with the complementary state H = I − H. Transmitters send the same signal (encoding the same message) in both states. Then after T occurrences of the first state receiver j decodes m j = ∑ n i=1 H ji m i , at rate D(Z) and after T occurrences of the complementary state decodes also at rate D(Z). Receiver j then computes the message estimate as desired. Since decoding the message required twice the blocklength, the rate is half what it would be, (log 2 TD(Z) )/2T = D(Z)/2.
(Observe that the receiver needs to perform two separate estimates, and cannot simply add the channel outputs together. To do this would lead to a channel of the form Y = x j + Z * Z , where the convolution Z * Z means the sum of two IID copies of Z. The overall rate in this case is D(Z * Z) ≤ D(Z)/2, unless Z is deterministic, with strict inequality unless D(Z) = 0 [47]. In general, the K-fold convolution has relative entropy from the uniform D(Z * · · · * Z) that usually decreases exponentially in K [47].) Nazer and coauthors use a typical set argument to show that sufficiently many channel states can be matched up in this way, showing that with high probability each matrix and its complement show up almost the same number of times. They use this to prove the following theorem [44, Lemma 3 and Theorem 2]: Theorem 2.14. For the model as outlined above, the rates r i = D(Z)/2 are simultaneously achievable.
Using a quantisation argument, they show the following [44, Theorem 3]: Theorem 2.15. For the fast fading Gaussian interference channel with symmetric fading (that is, H and −H have the same distribution), the rates r i = 1 2 E log(1 + 2SNR) are simultaneously achievable.
We will use this result more in Chapter 4.

Notes
The section consists of a review of the existing literature; the mathematical contents is not claimed to be new.
On networks, the textbook of Cover and Thomas [6,Chapter 15] and the review papers of El Gamal and Cover [48] and Kramer [49] were useful.
The first detailed study of the point-to-point link was by Shannon [4], of the multiple access network was by Ahlswede [21] and Liao [22], of the broadcast network was by Cover [24], and of the interference network was by Carleial [50].
The strategies of interference as noise, decode-and-subtract, and resource division are old and well-known, making tracking down details of their discovery difficult. The textbooks by Tse and Viswanath [5] and by Goldsmith [40] give good background on this material.
The concept of interference alignment -first discovered in the alignment by codeword choice paradigm -is due to Cadambe and Jafar [28], and also to Maddah-Ali, Motahari, and Khandani [51], who independently discovered a similar method (published in the same issue of the same journal).
The toy example of interference alignment by codeword choice is due to Jafar [52]. The example of interference alignment by time is after Grokop, Tse, and Yates [43]. Ergodic interference alignment was discovered by Nazer and coauthors [44].
A tutorial by Jafar [52] was useful for the material on interference alignment.

Regular and Poisson random networks
In this chapter, we look at two networks based on models of how nodes are positioned in space. In the regular network, nodes are positioned at regular spacings, as in a grid; in the Poisson random network, nodes are positioned at random according to a Poisson point process.
We examine how large networks can operate using simple 'interference as noise' techniques. In particular, we show the important relationship between the attenuation α of the signals (which describes how quickly signals die off over distance) and the dimension d of the network.

Model
We use the model of a Gaussian network with slow fading based on powerlaw attenuation. That is we have a countable set of points (nodes) placed in d-dimensional Euclidean space R d -each node i ∈ Z + is positioned at the point T i ∈ R d .
On the tth channel use, the signal received by node j is Here, ρ(i, j) = T j − T i is the Euclidean distance between nodes i and j. We call h the fixed fading parameter. Large h corresponds to signals being much more powerful than noise; small h corresponds to signals being much less powerful than noise. To concentrate on the interference-limited regime, we will sometimes consider the limit h → ∞, which is equivalent to the noiseless network with h = 1, The Euclidean norm in R d will be denoted , where d is the dimension of the network. It will be useful later to define which is the volume of the Euclidean unit ball in R d .
The d = 2 case is the most commonly studied, as this obviously has realworld applications. The case d = 3 has applications in, for example, tall office buildings; and the d = 1 is attracting more attention for 'car-to-car' protocols (see for example recent work by the US Department of Transportation [53]), where a long road can be modelled as a one-dimensional line.

Regular networks
In a d-dimensional regular network, (see for example Xie and Kumar [54]), nodes are placed at points of Z d in d-dimensional space R d . In particular, any two nodes are a distance at least 1 from each other.
Below we show regular networks in one and two dimensions respectively.
Each node t ∈ Z d is a transmitter, transmitting to one of its 2d nearest neighbours, chosen arbitrarily. We write t → r to indicate that node t transmits to node r.
All nodes will use standard Gaussian codebooks of power P = 1, generated independently of each other. This means that -power aside -signals are statistically indistinguishable from a) each other, and b) the background noise. We use the principle that interference should be treated as noise (as in Section 2.3).
Following Gupta and Kumar [35] the interference at any node r ∈ Z d and using interference-as-noise the communication rate That is, if the interference I is finite, then every node can transmit at this fixed rate. This is known as linear growth for the following reason: if we have a sequence of sets of nodes (S n : n ∈ N), where S n ⊂ Z is of cardinality n, then there exists an achievable rate n-tuple (r i : i ∈ S n ) such that ∑ j∈S n r j = nr = O(n).
The following theorem generalises the work of Xie and Kumar [54], who proved it for the case d = 2. First, the base case, d = 1. The interference is which is finite for α > 1, as desired.
The inductive hypothesis is that I(α, d − 1) is finite. Now the inductive step. Again, the interference is The first term in (3.2) is finite by the inductive hypothesis; we concentrate on the second term. By treating the point 1 = (1, 1, . . . , 1) separately, we have The second term in (3.3) can be approximated by an integral, since for t ∈ N d , Hence, where B(0, 1) is the d-dimensional unit ball centered at the origin. We now use a change of coordinates to ρ = t , s = t/ρ, so that dt = ρ d−1 dρ ds. This gives The inductive step is complete and the theorem is proven.
Note that this result is the best possible. (By 'best possible', we mean that Theorem 3.1 is not true for α ≤ d. We do not claim our bounds on I(α, d) are as tight as possible.) If α ≤ d, then the interference is and the signal-to-interference-plus-noise ratio is 0.
It is worth noting that a simple bound for I(α, d) is This can be proved inductively, using v(d) ≤ 2 d (that is, the volume of the unit sphere is less than that of the surrounding cube).

Poisson random networks
In this section, we define the Poisson random network, where nodes are distributed like a Poisson process. We give a local result -bounds on the outage probability of a single transmission -and a global result -showing that linear growth occurs in the network with high probability.

Node positioning model
In a d-dimensional Poisson random network (studied extensively by Haenggi [55,56], and Dhillon, Ganti, and Andrews [57], among others), the set of nodes {T i : i ∈ Z + } are placed in R d as a Poisson point process of density 1 (without loss of generality). For simplicity, we will translate the points such that T 0 is at the origin 0, and relabel the nodes by order of distance from the origin. So we have 0 = T 0 ≤ T 1 ≤ · · · (and strict inequalities almost surely). The figures below shows Poisson random networks in one and two dimensions.
t t t t t t -6 t that each node broadcasts its intended signal, whilst picking up the signal from its nearest neighbour. We will concentrate on the communication over just these short hops -the large-scale strategy has been studied by many others, particularly the multihop strategy of Gupta and Kumar [35] and the work on hierarchical cooperation byÖzgür, Lévêque, and Tse [37].
If node i's nearest neighbour is node j, we again write j → i. In particular, the nearest neighbour to node 0, at the origin, is node 1 at T 1 , so 1 → 0.
All nodes will use standard Gaussian codebooks of power P = 1, generated independently of each other. Nodes treat signals other than they are picking up as Gaussian noise, as discussed in Section 2.3.

Outage probability
Given the link j → i and the positions of nodes i and j, the position of other nodes in the network is random. In particular, for any given rate r > 0, we cannot guarantee that j can communicate to i at rate r. This is because the other nodes might (with non-zero probability) crowd round i, drowning out the intended signal from j.
Hence, we need to study the outage probability of the network (as discussed previously in Subsection 1.5.3).

Definition 3.2.
We define the outage probability as p out (r) = P r > log (1 + SINR ji ) .
Here (and throughout) P denotes probability over the Poisson point process.
The signal-to-interference-plus-noise ratio at node j, SINR ji , has marginal distribution function independent of the link i → j where the interference is From now on, we deal with the link 1 → 0, without loss of generality. We will suppress subscripts that are no longer necessary.
An important special case is the high power regime h → ∞, which is simpler to deal with mathematically and is important for studying networks that are interference limited rather than noise limited. Note that since this is equivalent to taking h = 1 and ignoring the noise term. The next two theorems give upper (Theorem 3.3) and lower (Theorem 3.4) bounds on the outage probability p out (r). The figure below shows these bounds for the common case d = 2, α = 3 in the high power h → ∞ regime.
In the high power h → ∞ regime, we have Note that since d the attentuation α and dimension d only enter this theorem through their ratio.
Proof. First, note that the outage probability can be rewritten as where we have defined s := 2 r − 1. So now we need only bound F SINR (s), the probability that SINR is large. We will bound F SINR (s) by conditioning on the position of the nearest neighbour. So It is known [58, Theorem 1] (and can be easily shown) that T 1 d has an exponential distribution with parameter v(d), We will also need to bound the probability that the interference is large, which we do using the conditional Markov inequality. Specifically, when 1 s ht −α − 1 > 0, we have (3.7) and when 1 s ht −α − 1 ≤ 0, we take the trivial bound 1 instead. We concentrate on the simpler high power scenario first. Note that in the limit h → ∞, we always have 1 s ht −α − 1 > 0. For the moment, we concentrate on the first argument. We can write where P (t) is the set of points of the Poisson process outside the ball of radius t about the origin. Using Campbell's theorem (see for example the monograph of Haenggi and Ganti [55, Theorem A.2]), we then have

Substituting (3.8) and (3.6) this back into equation (3.5) gives
where t * = s dv(d) is the point where we cross over from one argument of the 'min' to the other. Calculating these integrals using a substitution y = v(d)x d gives This proves the theorem for the high power regime. We now move back to the general case. Returning to (3.7), we now have where t * * = (s/h) −1/α is the point at which 1 s ht −α − 1 = 0. We could evaluate this integral numerically, or express it as a complicated sum of Gamma functions. Instead, we will show a simple bound.
When t ≤ 2 −1/α t * * , we have s h t α ≤ 1 2 , and hence This allows us to bound the integral by , as required, where the first term follows upon replacing the upper limit of the integral by ∞.

Theorem 3.4. Under the same conditions as Theorem 3.3, the outage probability is bounded below by
The key is to observe that the interference I is at least as large as the contribution coming from the second-nearest neighbour T 2 . That is, Rearranging this, we get where the final result follows on considering the probability that the annulus {u ∈ R d : t < u ≤ ts 1/α } is empty. Again, combining this with Equations (3.5) and (3.6), we obtain a lower bound on the outage probability of the form and the result follows on making the change of variables y = v(d)t d .

Linear growth
Recall that we say that linear growth occurs when the sum-rate of n users scales linearly with n. That is, if we have a sequence of sets of nodes S n : n ∈ N , where S n ⊂ Z + is of cardinality n, then there exists an achievable rate n-tuple (r i→j : i ∈ S n ) such that ∑ i∈S n r i→j = O(n).
In particular if a 'proportion' p of links were to support a given rate r, then we would have ∑ i∈S n r i→j ≈ pnr = O(n), which would be sufficient to show linear growth.
In particular, if communication on distinct links were independent, this would be true with p = 1 − p out (r). Although the links are not independent, links 'far enough away' are. Thus by splitting the network into 'close' and 'distant' nodes we can prove the theorem.

Theorem 3.5. Consider a d-dimensional Poisson random network with attenuation
α in the interference-limited h → ∞ regime. Suppose α > d. Then we have linear growth with probability tending to 1 as n → ∞ at rate O(n −(1−d/α) ).
The following Chernoff-type bound on Poisson random variables will be useful later.
Proof. We have, using Markov's inequality, We are now in the position to prove Theorem 3.5.
Proof of Theorem 3.5. First recall that h → ∞ is equivalent to taking h = 1 an deleteing the noise term. Let n be some fixed integer. (Later, we will consider the sum rate of n nodes, and let n → ∞.) Fix the nearest-neighbour link i → j.
Given a node j situated at the point T j , we divide the other nodes into those close to j C(j) where a is some parameter to be chosen later.
Outage occurs when the signal-to-interference-plus-noise ratio is insufficient to support some given rate r = log (1 + s). We will consider whether an outage event is caused primarily by close or distant nodes. Specifically, we define the events Note that if a link i → j is in outage, at least one of Out C (j) and Out D (j) must be occurring. Note also that the (marginal) distributions of Out C (j) and Out D (j) are independent of the node j. When the node index is irrelevant, we suppress it. Suppose n nodes all try to communicate at the rate r = log (1 + s). Then for ∈ (0, 1 2 ), ≤ P(number of outages ≥ 2 n) = P(number of distant outages ≥ n ∪ number of close outages ≥ n) ≤ P(number of distant outages ≥ n) + P(number of close outages ≥ n) We bound the two terms above separately.
For the first term in (3.9), by Markov's inequality, we have Using the same ideas as in the proof of Theorem 3.3, we can show that this term tends to zero for a > 0 at rate O(n −a(α−d) ). (The key is to change the lower limit in the integral in (3.8) to n a .) We bound the second term in (3.9) using the idea that for most j and k, C(j) and C(k) are disjoint, so the corresponding contributions will be independent.
Let N j denote the number of nodes whose 'close' regions overlap with j's 'close' region; that is Note that N j is the number of nodes in a ball of radius 2n a , so is Poisson with mean 2 d v(d)n ad .
We write N = {max 0≤j≤n−1 N j ≥ 2 d v(d)n ad e} for the event that one of the N j is particularly large. We will argue that the event N can be ruled out with high probability, allowing good control of the growth of the variance.
We exploit the fact that, conditioned on the event N c , for any j there are at most 1 + 2 d v(d)n ad e indices k such that Cov 1[Out C (j)], 1[Out C (k)] | N c is non-zero, and each such covariance is no greater than 1. Hence we can control the growth of the variance of the sum as (3.10) By the union bound and Lemma 3.6, we have Using the law of total probability, and substituting (3.10) and (3.11) into Chebyshev's inequality gives As we send n → ∞, this tends to 0 at rate O(n ad−1 ). Setting a = 1/α means the two terms both tend to 0 at rate as desired.

Further work
The strength of a Poisson model is the extensibility and mathematical flexibility of the Poisson point process.
For just one example, in a spatially inhomogeneous Poisson process, there is a density function λ : R d → R + , such that the number of nodes in some region A is Po

Notes
The new work in this chapter is joint work with Oliver Johnson and Robert Piechocki. It has not previously been published, although the research was conducted prior to some since-published work [59,55] The monographs of Baccelli and Błaszczyszyn [59] and Haenggi and Ganti [55] were useful background on the SINR approach to stochastic networks, as was the work of Haenggi [56], Xie and Kumar [54], and Gupta and Kumar [35].
The textbook of Kingman [60] was useful background material for Poisson processes.

4
Sum-capacity of random dense Gaussian interference networks In this chapter, we will find approximations to the sum-capacity of interference networks with many users. Our interference networks will be motivated by physical models of wireless networks. When we say many users, we will be allowing the number of users n to tend to infinity, and looking at asymptotic behaviour. We will be doing this without expanding the area in which the nodes reside, so the nodes will get packed closer and closer together -for this reason, such networks are called dense networks.
We will model transmitters and receivers as being placed randomly in space. This means that signal-and interference-to-noise ratios will be random too, but fixed for the duration of communication -and hence a form of slow fading.
The crucial insight to prove these results is that the performance in these networks is tightly constrained by the performance on a few so-called bottleneck links. Ideas from interference alignment (specifically ergodic interference alignment) are crucial in performing well on these links, and hence in the whole network.
The main result (Theorem 4.3) will be to show, for the model we will consider, that the sum-capacity C Σ is roughly n 2 E log(1 + 2SNR). Specifically, we show that C Σ /n converges in probability to 1 2 E log(1 + 2SNR) as n → ∞. In this chapter, random positions will give a form of slow fading, and we will also add fast fading, to make a realistic model of real-world networks.
All results in this chapter hold provided that this fast fading is symmetrical (in the sense that H ji and −H ji are identically distributed, for all i and j).
For simplicity and concreteness, we will choose to give all our results in the context of random phase fading, so In Section 4.6, we briefly discuss how to apply other fading models such as Rayleigh fading.

Introduction
Recently, progress has been made on many-user approximations to the sumcapacity C Σ of random Gaussian interference networks.
In particular, in a 2009 paper, Jafar [27, Theorem 5] proved a result on the asymptotic sum-capacity of a particular random Gaussian interference network: Theorem 4.1. Suppose direct SNRs are fixed and identical, so SNR i = snr for all i, and suppose that all INRs are IID random and supported on some neighbourhood of snr. Then the average per-user capacity C Σ /n tends in probability to 1 2 log(1 + 2snr) as n → ∞.
We examine Jafar's result in detail later.
(Here and elsewhere, we use C Σ to denote the sum-capacity of the network, and interpret C Σ /n as the average per-user capacity.) A subsequent result by Johnson, Aldridge and Piechocki [1, Theorem 4.1] concerned a more physically realistic model, the standard dense network: Theorem 4.2. Suppose receivers and transmitters are placed IID uniformly at random on the unit square [0, 1] 2 , and suppose that signal power attenuates like a polynomial in 1/distance. Then the average per-user capacity C Σ /n tends in probability to 1 2 E log(1 + 2SNR) as n → ∞.
In this chapter, we prove a similar, but more general, result to Theorem 4.2, with a neater proof, using ideas from Jafar's proof of Theorem 4.1. We assume transmitters and receivers are situated independently at random in space (not necessarily uniformly), and that the power of a signal depends in a natural way on the distance it travels.
Specifically our result is the following (full definitions of non-italicised technical terms are in Section 4.2): Theorem 4.3. Consider a Gaussian interference network formed by n pairs of nodes placed in a spatially separated IID network with power-law attenuation. Then the average per-user capacity C Σ /n converges in probability to 1 2 The direct part of the proof uses interference alignment; specifically, we take advantage of ergodic interference alignment (see Section 2.6).
The converse part of the proof uses the idea of 'bottleneck links' developed by Jafar [27]. An information theoretic argument gives a capacity bound on such bottleneck links, and probabilistic counting arguments show there are sufficiently many such links to tightly bound the sum-capacity of the whole network.
Before going any further, we should mention two similar results in the same area using different interference alignment techniques.
A paper byÖzgür and Tse [61] proves linear scaling in interference networks by showing that for any value of snr and n, the sum-rate is bounded below by k 1 n log(1 + k 2 snr), where k 1 , k 2 > 0 are universal constants.
Secondly, a paper by Niesen [62] bounds the capacity region (rather than just the sum-capacity) of arbitrary dense networks, albeit with a factor of O(log n) separating the inner and outer bounds.

Model
We outline the model we will use. We will model separately how messages are transmitted, and how nodes are positioned.
These ideas were introduced in an earlier paper [1], but were not fully exploited, due to that paper's concentration on the standard dense network.

Communication model
We will use the n-user Gaussian interference network as our main model. That is, we have The fading coefficients H ji [t] will be made up of a fast fading part, representing the moment-to-moment changes in the channel, and a slow fading part, the power attenuation due to node placing.
The results require the fast fading to be symmetric, in that H ji and −H ji are identically distributed -this is ensured by the random phase we use (and is also satisfied by Rayleigh fading). For ease of notation and to simplify exposition, will assume the fast fading takes the form of a (uniformly) random phase change (although we briefly discuss more general models in Section 4.6). Therefore, we can write the fading coefficients in modulus-argument form as where the Θ ji [t] are IID uniform on [0, 2π), and SNR i = |H ii | 2 and INR ji = |H ji | 2 are the squared moduli (which are constant over time). Our results are in the context of so-called 'line of sight' communication models, without multipath interference. That is, we consider a model where signal strengths attenuate deterministically with distance according to some function a. We We consider the n-user Gaussian interference network. So transmitter i sends a message encoded as a codeword x i = (x i [1], . . . , x i [T]) to receiver i, under a power constraint 1 T ∑ T t=1 |x i [t]| 2 ≤ 1 for each i. The tth symbol received at receiver j is given as where the noise terms Z j [t] are independent standard complex Gaussian random variables, and the phases Θ ji [t] are independent U[0, 2π) random variables independent of all other terms. The INR ji and SNR i remain fixed over time, since the node positions themselves are fixed, but the phases are fastfading, in that they are renewed for each t.

Definition 4.5.
We say an attenuation function a has power-law attenuation if there exist constants α and k att such that for all ρ, we have a(ρ) ≤ k att ρ −α .
For brevity, we write S ji for the random variables 1 2 log(1 + 2INR ji ) (when i = j), and S ii for 1 2 log(1 + 2SNR i ) which are functions of the distance between the transmitters and receivers. In particular, since the nodes are positioned independently, under this model the random variables S ji are identically distributed, and S ji and S lk are IID when {i, j} and {k, l} are disjoint.
We will also write E = ES ii = 1 2 E log(1 + 2SNR), noting that this is independent of i. (It is also true that E = ES ji for all i and j.) Lemma 4.12 later ensures that E is indeed finite.

Node position model
We believe that our techniques should work in a variety of models for the node positions. We outline one very natural scenario here. Definition 4.6. Consider two probability distributions P T and P R defined on d-dimensional space R d . Given an integer n, we sample n transmitter node positions T 1 , . . . , T n independently from the distribution P T . Similarly, we sample n receiver node positions R 1 , . . . , R n independently from distribution P R . We refer to such a model of node placement as an IID network.
(Equivalently, we could state that transmitter and receiver positions are distributed like two independent non-homogeneous Poisson processes, conditioned such that there are n points of each type.) We pair the transmitter and receiver nodes up so that transmitter i at T i wishes to communicate with receiver i at R i for each i.
Transmitters and receivers that are very close to each other will lead to very strong interference or signals. These extreme occurences could prevent the network from operating as we would like. Also, as we remarked in Section 1.4, our attenuation models lose physical accuracy at very small distances. For this reason, we will demand that our node positioning model ensures that this is rare, a property we call spatial separation. Definition 4.7. Let T ∼ P T and R ∼ P R be placed independently in R d . We say the IID network is spatially separated if there exists constants β > 0 and k sep such that for all ρ P( R − T ≤ ρ) ≤ k sep ρ β .
In particular, we can show that the standard dense network is spatially separated.
Definition 4.8. The d-dimensional standard dense network is an IID network defined by P T and P R being independent uniform measures on [0, 1] d .
The standard dense network is spatially separated.
Proof. We need to show that Definition 4.7 is fulfilled. By conditioning on T = t, we get The standard dense network has been the subject of much research (see the review paper of Xue and Kumar [36] and references therein). However, we emphasise that our result holds for a wider range of models.

Jafar network
We now review in more detail Jafar's important result. We call a network with fixed equal snrs and IID INRs a Jafar network. (Note that the Jafar network cannot be written as an IID network with power-law attenuation.) Theorem 4.1 restated. Suppose direct SNRs are fixed and identical, so SNR i = snr for all i, and suppose that all INRs are IID random and supported on some neighbourhood of snr. Then the average per-user capacity C Σ /n tends in probability to 1 2 log(1 + 2snr) as n → ∞.
Proving the direct part of this result is simple: the central result of ergodic interference alignment (Theorem 2.15) tells us that the rates 1 2 log(1 + 2snr) are simultaneously achievable by all users.
For the converse part, Jafar defines [27, proof of Theorem 5] the crosslink i → j as being a -bottleneck link if the sum-capacity of the two-user network with links i→i and j→j with crosslink i→j has sum-rate bounded by for some fixed > 0. Analysis of these bottleneck links then gives the converse result. We will use a similar method to this to prove our main result (Theorem 4.3). We will need to alter the definition of bottleneck links slightly to fit our needs. Also, the entire converse part is made more complicated: while the Jafar network has lots of convenient independences between the snr and INRs, we are not so lucky. Therefore extra care must be taken.
We also give here an alternative proof of Theorem 4.1. This proof uses techniques from graph theory, and gives a faster rate of convergence than Jafar's own proof -exponential, rather than O(n −2 ).
Alternative proof of Theorem 4.1. We need to show that every user is involved in a bottleneck link. We will first review some facts from random graph theory.
Form a random bipartite graph by taking two sets V, W of vertices each of size K, and making each edge from V to W present independently with probability δ (there are no edges within either V or W). A matching is a set of k of the edges such that every vertex in the graph is adjacent to one edge -so each vertex v ∈ V is matched to a vertex w ∈ W by an edge vw.

V W
A classical result due to Erdös and Rényi [63, Theorem 2] (originally stated in terms of random matrices) states that the probability that a matching fails to exist tends to 0 for any δ = δ(K) = (log K + ω(1))/K, where ω(1) is, using Bachmann-Landau asymptotic notation, a term that tends to ∞.
We recall the argument where δ is a fixed constant, so that we can be precise about the bounds, rather than just working asymptotically. Following Walkup [64, Definition 1], we say that a subset V ⊆ V of size k and a subset W ⊆ W of size K − k + 1 form a blocking pair of size k if no edge of the graph connects V to W. Walkup [64, Section 3] uses König's theorem (equivalently one can use Hall's marriage theorem) to deduce that We split this sum into the terms where k ≤ √ K and those where k > √ K. Using the bounds we get the bound We deduce that the probability of a complete matching failing to exist decays at an exponential rate in K.
We can now prove Theorem 4.1. Construct a random bipartite graph by dividing the receiver-transmitter links into two groups V and W of size K = n/2. Choose > 0 and, for i ∈ V and j ∈ W include the edge ij if either of the crosslinks i → j or j → i is an -bottleneck link, which in the Jafar network occurs independently with some probability δ.
We seek a matching on this graph. For each pair (i, j) that is successfully matched up, the corresponding two-user channel is an -bottleneck, and hence has the bound r i + r j ≤ log(1 + 2snr) + by (4.1). for any achievable rates. If every edge is matched this way, we have The high probability of a matching existing implies exponential decay of proving the theorem with exponential convergence.
For our IID networks, extra dependencies between links make the picture much more difficult, so we have been unable to find a proof that extends this random bipartite graph method. Whether or not exponential convergence holds for IID networks with power-law attenuation is an open problem.

Proof: achievability
We can now prove our main theorem, Theorem 4.3, by breaking the probability into two terms, which we deal with separately. So Bounding the first term of (4.2) corresponds to the achievability part of the proof. Bounding the second term of (4.2) corresponds to the converse part, and represents our major contribution.
We prove the direct part using ergodic interference alignment.
Proof. The first term of (4.2) can be bounded relatively simply, using ergodic interference alignment. A theorem of Nazer, Gastpar, Jafar, and Vishwanath (Theorem 2.15 of this thesis) implies that the rates This allows us to bound the first term in (4.2) as But E = ES ii , so this probability tends to 0 by the weak law of large numbers.

Proof: converse
We now need to show that the second term of (4.2) tends to 0 too. Specifically, we must prove the following: for all > 0 The proof of the converse part is the major new part of this chapter. First, bottleneck links are introduced, and we prove a tight information-theoretic bound on the capacity of such links. Second, a probabilistic counting argument ensures there are (with high probability) sufficiently many bottleneck links to bound the sum-capacity of the entire network.

Bottleneck links
The important concept is that of the bottleneck link, an idea first used by Jafar [27] and later adapted by Johnson, Aldridge, and Piechocki [1] in the following form: Definition 4.10. We say the link i→j, i = j, is an -bottleneck link, if the following three conditions hold: We let B ij be the indicator function that the crosslink i→j is a -bottleneck link. We also define the bottleneck probability β := E B ij to be the probability that a given link is an -bottleneck which is independent of i and j for an IID network. (We suppress the dependence for simplicity.) This definition does have a physical interpretation (although the only motivation for it is that it allows us to prove the bound in Lemma 4.11).
The physical interpretation is this: fix the position T i of transmitter i. Condition B1 requires that receiver i is sufficiently far away from T i , and condition B2 requires that receiver j is sufficiently far away too. Condition B3 requires that transmitter j is closer to receiver j than to receiver i.
The crucial point about bottleneck links is the constraints they place on achievable rates in a network. Lemma 4.11. Consider a crosslink i→j in a n-user Gaussian interference network. If i → j is a -bottleneck link, then the sum of their achievable rates is bounded by r i + r j ≤ 2E + .
Proof. First, note that we make things no worse by considering the two-user subnetwork: where receiver i needs to determine message m i , and receiver j message m j .
(The time index is omitted for clarity.) From bottleneck conditions B1 and B2 we have Summing and taking logs gives We combine this with the argument given by Jafar [27], which we discussed earlier (Section 2.3). Let r i and r j be jointly achievable rates for the subnetwork. In particular, receiver i can determine message m i with an arbitrarily low probability of error.
We certainly do no worse if a genie presents message m i to receiver j, so we assume receiver j can indeed recover m i . But condition B3 ensures that it is easier for receiver i to determine m j than it is for receiver j (since the weighting is larger in the first case). So since receiver j can recover m j (as r j is achievable), receiver i can recover m j also.
Because receiver i can determine both m i and m j , these two signals must have been transmitted at a sum-rate no higher than the sum-capacity of the Gaussian multiple-access channel (Theorem 2.8). Hence, where the second inequality comes from (4.4).

Three technical lemmas
A few technical lemmas are required in order to prove (4.3).
First, we need to ensure that very high SNRs are very rare (Lemma 4.12). Second, we need to show that bottleneck links will actually occur (Lemma 4.13). Last, we must show that the number of bottleneck links cannot vary too much (Lemma 4.14). Under any network model where these three lemmas are true, our theorem will hold. We emphasise that our model of IID networks with power-law attenuation is one such model; we believe the result holds more widely. Lemma 4.12. Consider a spatially separated IID network, with power-law attenuation. Then for any η > 0, In fact, in our case convergence to 0 is considerably quicker than O(n −1 ), but this is sufficient.
Proof. First, we have by the union bound Now we apply the definition of S 11 := 1 2 log(1 + 2SNR) and recall that Since a is a power-law attenuation function, we have and since the network is spatially separated, we have (and obviously much tighter than O(n −2 )). Together with (4.5), this gives the result.
(It is worth noting that this fast decay in the tails of S ii ensures that the expectation E = ES ii does indeed exist and is finite.) We will often condition off this event; that is, condition on the complementary event {max S ii ≤ n η/2 }. We use P n , E n and Var n to denote such conditionality, and write β n = E n B ij for the conditional bottleneck probability.
The next two lemmas concern showing that conditional probabilities are nonzero. However, we have for any event A, P(A) = P(A | max S ii ≤ n η/2 )P(max S ii ≤ n η/2 ) + P(A | max S ii > n η/2 )P(max S ii > n η/2 ). and hence by Lemma 4.12 we have the two bounds and so P(A) = P n (A) + O(n −1 ). (4.6) This will be useful in the next two proofs.
Lemma 4.13. Consider a spatially separated IID network, with power-law attenuation. Then the conditional bottleneck probability β n is bounded away from 0 for all n sufficiently large.
Proof. First note that by (4.6), we need only show that the unconditional bottleneck probability β is nonzero. Second, note that by the exchangeability of R i and R j , we have P(B1 and B2 and B3) ≥ 1 2 P(B1 and B2).
It is left to show that P(B1 and B2) is non-zero. Note that B1 requires S ii to be less than its expectation plus . So R i must be situated such that this has nonzero probability. So T i has a nonzero probability of being positioned such that B1 occurs. But T i and T j are also exchangeable, so we are done. Lemma 4.14. Consider a spatially separated IID network with power-law attenuation. Then, conditional on {max i S ii < n η/2 }, where the sum is over all crosslink pairs (i, j), i = j.
In general, one might assume that Var n (# bottleneck links) would be proportional to the square of the total number of links, and thus be O(n 4 ). However, because of the independences in the IID network, the variance is in fact much lower.
Proof. First consider the unconditional version. We have The important observation is that for i, j, k, l all distinct, B ij and B kl are independent giving Cov(B ij , B kl ) = 0. (This is because they depend only on the position of distinct and independently-positioned nodes.) Hence there are only O(n 3 ) non-zero terms in the sum. Each non-zero covariance term in the sum is bounded by variance of the indicator function, so But by (4.6), if Cov(B ij , B kl ) = 0, then the conditional covariance is very small Cov n (B ij , B kl ) = O(n −1 ). Hence, as desired.

Completing the proof
We are now in a position to prove (4.3), and hence prove Theorem 4.3.
Proof. We need to show So choose > 0, δ > 0, fix n ≥ N (where N will be determined later), and pick a fixed rate vector r ∈ R n + with sum-rate r Σ n > E + ; (4.7) we need to show that P(r is achievable) ≤ δ. (Here, we are writing r Σ := ∑ n i=1 r i for the sum-rate.) We divide into two cases: when there is a very high SNR, which is unlikely to happen; and when there is not, in which case r is unlikely to be achievable. Formally, P(r achievable) = P(r achievable | max S ii ≤ n η/2 )P(max S ii ≤ n η/2 ) for n sufficiently large, by Lemma 4.12. We need to bound the first term in (4.8).
First, note that our assumption on max i S ii means that if r i > 2n η/2 , then we break the single-user capacity bound, since we would have meaning r is not achievable, and we are done. Thus we assume this does not hold; that r i ≤ 2n η/2 for all i. Now, if r is achievable, it must at least satisfy the constraints on thebottleneck links i→j from Lemma 4.11, and hence also the sum of those constraints. So P n (r achievable) ≤ P n (r i + r j ≤ 2E + on bottleneck links i→j) where we have defined The conditional expectations of U and V are E n U = 2β n r Σ n , E n V = β n (2E + ) = 2β n E + 2 .
Note that since β n > 0 by Lemma 6, we can rewrite (4.7) as E n U > E n V + β n , or equivalently, The proof is completed by formalising the following idea: since the expectations are ordered E n U > E n V, we can only rarely have the opposite ordering U < V. Hence the expression in (4.10) is small. Formally, by (the conditional version of) Chebyshev's inequality and the union bound, we have  Using Lemma 4.14 we can bound these variances as 1−η) ).
where we used (4.9) to bound Var n U. Choosing η to be less than 1, we can ensure N is sufficiently large that for all n ≥ N, This makes (4.11) into P n (U ≤ V) < δ/2. Together with (4.10) and (4.8), this yields the result.

Conclusion
In this chapter we have defined IID interference networks with power-law attenuation. We have shown that this setup fulfills necessary properties for the average per-user capacity C Σ /n to tend in probability to 1 2 E log(1 + 2SNR). We have also noted that this result is not unique to our setup. We briefly mention one more example.
Suppose, for example, that Rayleigh fading is added to our model. That is, now let SNR i := |H ii | 2 a( T i − R i ) and INR ji := |H ji | 2 a( T i − R j ), where the H ji are IID standard complex Gaussian random variables.
Because ergodic interference alignment still works with Rayleigh fading [44, Section IV], the direct part of the theorem still holds. But also, because the fading coefficients are IID, the independence structure from the non-fading case remains, ensuring Lemmas 4.12-4.14 hold. Hence, the theorem is still true.
Characterising all networks for which such a limit for average per-user capacity exists is an open problem.
At the moment, Theorem 4.3 should perhaps be regarded as being of theoretical interest. That is, our major contribution is to provide a sharp upper bound on the performance of interference networks. However, the lower bound relies on an ergodic interference alignment which, while rigorously proved, may not be feasible to implement in practice for large number of users. Examination of the proof of the effectiveness of ergodic interference alignment [44,Theorem 1] shows that, even for a model with alphabet size q, the channel needs to be used O((q − 1) n 2 ) times. Even for n ∼ 10, this is a prohibitive requirement. We approach this problem in the next chapter.

Notes
The new work in this chapter -specifically Theorem 4.3 and its proof, and the definition of the IID network -is joint work with Oliver Johnson and Robert Piechocki. This chapter is based on two papers we wrote [1,2]. This work benefited from the advice of anonymous reviewers for from IEEE Transactions on Information Theory and the 2010 IEEE International Symposium on Information Theory.
The ideas in this chapter were first studied by Jafar [27] -in particular, the concept (although not the exact definition) of bottleneck links comes from that paper.
The earlier of our two papers [1] (which actually appeared in publication later) considered only the standard dense network, but defined many of the important concepts in this chapter. The full general proof was first published in the later of our two papers [2] (which appeared earlier).
With the exception of our new proof of Theorem 4.1 from our earlier paper [1], the material on Jafar networks (Section 4.3) is due to Jafar.
Delay-rate tradeoff for ergodic interference alignment

Introduction
Earlier, in Section 2.8, we discussed the ergodic interference alignment scheme of Nazer, Gastpar, Jafar, and Viswanath (which we hereafter to refer to as the NGJV scheme).
Recall that we considered a model of communication over a finite field F q of size q. Since the NGJV scheme (see Section 2.8) requires a particular n × n channel matrix with entries in F q \ {0} to occur, the expected delay for a particular message is (q − 1) n 2 (which is roughly q n 2 for large q). It is clear that even for n and q relatively small, this is not a practical delay. (For n = 6 and q = 3, for example, the delay is 2 36 ≈ 7 × 10 10 .) There are five questions we would like to try to answer: 1. Can we find a scheme that, like NGJV, achieves half the single-user rate, but at a lower time delay?
2. Can we find schemes that have lower time delays than NGJV, even at some cost to the rate achieved?
3. Specifically, which schemes from Question 2 perform well for situations where we have few users (n small)?
4. Specifically, which schemes from Question 2 perform well for situations where we have many users (n → ∞)?
5. What is a lower bound on the best time delay possible for any scheme achieving a given rate for a given number of users?
In Sections 5.3 and 5.4, we define a new set of schemes, called JAP (Subsection 5.3.1), a beamforming extension JAP-B (Subsection 5.3.4), and child schemes derived from them (Section 5.4) that have lower time delays than the NGJV scheme, for a variety of different rates, answering Question 2. As a special case, examined in Subsection 5.3.5, the JAP-B([n]) schemes achieve half the single-user rate, like NGJV, while reducing the time delay from q n 2 to q (n−1)(n−2) , answering Question 1. In Section 5.5, we answer Questions 3 and 4, by finding and analysing the JAP schemes that perform the best for small and large n; the table on page 109 and the graphs on page 110 illustrate the best schemes for small n, and Theorems 5.6 and 5.7 give the asymptotic behaviour of the schemes. Question 5 remains an open problem (although we do give a lower bound on the delay achievable for the schemes listed above).
Koo, Wu, and Gill [65] have previously attempted to answer Questions 2 and 3. We briefly outline their work at the end of Section 5.2.

Model
We give our results in the context of the finite-field interference network with fast-fading.
Recall that the single-user capacity of this channel is log q − H(Z) =: D(Z). Extending our previous definition of degrees of freedom (Definition 1.13) to multiple users, we have the following: Definition 5.1. Given an achievable symmetric rate point (r, r, . . . , r), we define the symmetric per-user degrees of freedom to be dof = r/D(Z).
In particular, it's clear that a single user can achieve 1 degree of freedom. We define the expected time delay for the NGJV scheme to be the average number of time slots we must wait after seeing a channel matrix H until we see the corresponding matrix I − H. The time delay is geometrically distributed with parameter p, where p is the probability that the random channel matrix takes the value I − H. The mean of this random variable is 1/p; hence the problem of finding the average time delay is reduced to a problem of finding the probability that a desired matrix appears in the next time slot. Since a channel matrix has n 2 entries, each of which needs to take the correct one value of q − 1 possible values, the average time delay is (5.1) (Here and elsewhere, we write f (q) ∼ g(q) if f (q)/g(q) → 1 as q → ∞.) As we mentioned before, this expected delay will be quite large even for modest values of q and n. For this reason, we will concentrate on the delay exponent.

Definition 5.2.
An interference alignment scheme with expected delay D ∼ kq T for some k and T has delay exponent T and delay coefficient k. More specifically, we have T := lim q→∞ log D/ log q.
We regard reduction of the delay exponent as the key aim, with the delay coefficient playing a secondary role. In particular, the finite field model is in some sense an abstraction of the model where channel coefficients are Gaussians quantized into a set of size q, where q is chosen large enough to reduce quantization error. When q is large, the delay exponent T dominates the delay coefficient k in determining size of the expected delay D.
From Theorem 2.14, we know that the NGJV schemes achieve dof = 1/2, and we have just shown in (5.1) it requires a delay exponent of n 2 .
We also mention some new schemes outlined in a recent paper by Koo, Wu, and Gill [65]. They attempted to answer our Questions 2 and 3, by finding schemes -we call them KWG schemes -with lower delay than the NGJV scheme. The KWG schemes suggest matching a larger class of matrices than simply H and I − H. By analysing the hitting probability of an associated Markov chain, they were able to reduce the expected delay, at the cost of a reduction in rate (and hence degrees of freedom). However, their schemes only affect the delay by a constant multiple, with the shortest-delay scheme only reducing the delay to 0.64(q − 1) n 2 ∼ 0.64q n 2 with a sum-rate of 0.79D(Z) [65, page 5]. That is, the KWG schemes only reduce the delay coefficient k, leaving the delay exponent as T = n 2 . For modest q and n (say q = 3, n = 6, again), we regard this delay as still impractical. Since the KWG schemes achieve a lower rate than the NGJV scheme for the same delay exponent, we shall only compare our results with the NGJV scheme.

Three important observations
In the NGJV scheme, all receivers were able to decode their message by summing their two pseudomessages In other words, the NGJV scheme relies on the linear dependence This scheme has a large delay, because, given H[t 0 ], there is only one matrix, H[t 1 ] = I − H[t 0 ], that can complete the linear dependence. If there were a large collection of matrices that could complete the dependence, then the delay would be lower.
We make three observations to this end. First, while NGJV matches two channel states H[t 0 ] and H[t 1 ] to form this linear dependence, we could use more than two. That is, if we have K + 1 channel matrices than receivers j can sum the K + 1 pseudomessages to recover their message, Note that the transmission of a single message is now split among K + 1 channel states, rather than 2 as in NGJV. This means that the degrees of freedom of this scheme is reduced to 1/(K + 1) from NGJV's 1/2.
Second, any linear combination of channel state matrices that sums to I is sufficient. That is, if there exist scalars λ 0 , λ 1 ∈ F q such that then all receivers can recover their message by forming the linear combination of pseudocodewords Third, NGJV requires all receivers to be able to decode their messages at the same time. However, receiver j can decode its message if regardless of whether this equality holds for other receivers as well. In other words, receiver j can decode its message if Putting these three observations together, we make the following conclusion: Let H[t 0 ], H[t 1 ], . . . , H[t K ] be a sequence of K + 1 channel state matrices. If there exist scalars λ 0 , λ 1 , . . . , λ K such that for some j then receiver j can recover its message by forming the linear combination of pseudocodewords In fact, we only require since the coefficients λ k can be rescaled to make the top equation (5.2) equal to 1 without breaking the bottom equation (5.3). Or, writing h int j for the interference vector we can again rewrite the requirement as If n equalities like the (5.4) and (5.5) above hold, we say that "receiver j can recover its message from The time delay of this scheme is t K − t 0 .
Recall that the average delay is the reciprocal of the probability that a random matrix allows a receiver to recover its message. Thus it will be useful to note the following lemma.

Lemma 5.3. Conditional on the interference vectors
being linearly dependent, the probability that receiver j can recover its message is 1 − O(q −1 ).
Note that we only use a matrix when we know for certain that it fulfills our desired criteria -we merely need to know what the probability is that the next matrix will do, in order to calculate the expected delay.
Proof. Since the interference vectors are linearly dependent, there exists a linear combination where L > 0 of the λ k are nonzero. Thus, receiver j can recover its message provided that the corresponding linear combination is nonzero; call the probability that this happens p. When λ k = 0, then λ k H jj [t k ] =: V k is uniform on F q \ {0}, and when λ k = 0, then λ k H jj [t k ] = 0 too. So (5.6) is the sum of L random variables V k IID uniform on F q \ {0}. We can write the mass function of each V k as (1 + ρ)U − ρδ 0 , where U is uniform on F q , δ 0 is a point mass on 0, and ρ = 1/(q − 1). Then the mass function of the L-fold convolution is Hence, the probability that (5.6) is zero is The result follows.

The scheme JAP(a)
We now present our new scheme.
The idea behind the scheme is as follows: We start by seeing some channel state H[t 0 ]. We then set t 1 to be the first time slot that allows receivers 1 to a 1 to recover their message (where a 1 is decided on in advance). Next, we set t 2 to be the first time slot that allows receivers the next a 2 receivers to recover their message. And so on, until all n receivers have recovered their message.
Specifically, fix K ≤ n and a sequence [a 1 , a 2 , . . . , a K ] =: a of length K and weight n; that is, in the set A(n, K) := a ∈ Z K + : We write A k for the partial sums A k := a 1 + a 2 + · · · + a k (so in particular A 1 = a 1 and A K = n).
Then we define the scheme JAP(a) as consisting of the following K + 1 steps: Step 0: Start with a matrix H[t 0 ].
Step 1: Set t 1 to be the first timeslot that allows the first a 1 receivers 1, 2, . . . , A 1 to recover their message from H[t 0 ], H[t 1 ].
Step k: Set t k to be the first timeslot that allows the next a k receivers A k−1 + 1, A k−1 + 2, . . . , A k to recover their message from . . .
Step K: Set t K to be the first timeslot that allows the final a K receivers A K−1 + 1, A K−1 + 2, . . . , A K to recover their message from By the end of this process, all n = A K receivers have recovered their message.
Since the message was split over K + 1 time slots, the common rate of communication is D(Z)/(K + 1), which corresponds to dof = 1/(K + 1).

Delay exponent of JAP schemes
We now examine the delay exponent for our new schemes.
Theorem 5.4. Consider the n-user finite field interference network. Fix K and a ∈ A(n, K). We use the scheme JAP(a) as outlined above. Then 1. the expected time for the kth round to take place is D ∼ q T k (a) , where T k (a) = a k (n − k − 1); 2. the delay exponent for the whole scheme is Proof. Recall that the expected delay is the reciprocal of the probability the desired match can be made.
Suppose we are about to begin stage k of a scheme JAP(a). By Lemma 5.3, the probability we can complete the stage is 1 − O(q −1 ) multiplied by the probability that the interference vectors for the next a k receivers are linearly dependent. If the first k − 1 interference vectors are already linearly dependent, then we are done (with high probability, by Lemma 5.3). Assume they are not.
Write S for the span of the first k − 1 interference vectors for one of the desired a k receivers j, so Since all possible interference vectors in (F q \ {0}) n−1 are equally likely, the probability that the next matrix completes a linear dependence is where s is the proportion of vectors in S with no zero entries. By counting the possible coefficients in F q used in the span, the inclusion-exclusion formula gives us Hence, the desired probability is (where the 1 − O(q −1 ) term comes from Lemma 5.3).
Note that this is the same rate as is achieved by the original NGJV scheme, but that the delay exponent has been reduced from NGJV's n 2 to For small n in particular, this is a worthwhile improvement (see figure, p. 110).

Child schemes: using time-sharing
Another way to generate new alignment schemes is by time-sharing schemes designed for a smaller number of users.
Call the NGJV, KWG, JAP and JAP-B schemes 'parent schemes'. Given a parent scheme for the m-user network, we can modify for the any n-user network with n > m, giving what we call a 'child scheme'.
Specifically, we use resource division by time (see Subsection 2.6.1) to split the network into ( n m ) subnetworks, each of which contains a unique collection of just m < n of the users. Within each of these m-user subnetworks, a parent scheme is used, while the other n − m transmitters remain silent.
Resource division by time is often known as time-division multiple access or TDMA -we use that abbreviation in the rest of this chapter.
Such a child scheme clearly has the same delay exponent as the parent scheme, with the rate -and thus the degrees of freedom -reduced by a factor of m/n. So an m-user JAP-B scheme shared between n users gives dof = m/n(K + 1).
In particular, time-sharing the NGJV schemes for smaller networks gives a collection of schemes with a lower delay exponent m 2 < n 2 than the main NGJV scheme for a given number of users, reducing the degrees of freedom from 1/2 to m/2n.
(We are not aware that the idea of time-sharing NGJV schemes has previously appeared in the literature. However, the idea seems simple enough that we regard this as the 'current benchmark' against which we should compare our new schemes.) Interestingly, it seems that child schemes derived from time-sharing an NGJV-like JAP-B([n]) parent scheme are particularly effective, and very often performs better than other JAP-B schemes. We discuss this point further in the next section.

General case
Given a number of users n and a desired number of degrees of freedom dof = 1/(K + 1), we wish to find a scheme with the lowest delay exponent.
For K ≤ n − 2 the best parent scheme will be a JAP-B scheme with parameter vector a ∈ A(n, K). We write T(n, K) for this best delay exponent, that is T(n, K) := min a∈A(n,K) We can bound T(n, K) as follows.
Theorem 5.6. Fix n and K ≤ n − 2. For T(n, K) as defined above, we have the following bounds: The gap between the upper and lower bounds grows linearly with n.
The following lemma on partial harmonic sums will be useful.
Lemma 5.7. Let S(n, K) be the partial harmonic sum Then we have the bounds Of course, tighter bounds are available by comparing ∑ 1/k to 1/x dx, but this suffices for our needs.
where we have used Lemma 5.7. Rearrangement gives the lower bound.
An upper bound is obtained by using the same c and taking This gives where we have used Lemma 5.7. Rearrangement gives the upper bound.

Few users: small n
For small values of n, we can find the best parent JAP-B schemes by hand.
(The task is simplified by noting that the optimal a k will be nonzero and increasing in k.) The table below gives the delay exponents of the best JAP-B schemes for n = 3, . . . , 8 and K ≤ n − 2.
Best JAP-B(a) schemes for small values of n and K, and their delay exponents. n = 3 n = 4 n = 5 n = 6 n = 7 n = 8

Many users: n → ∞
We now consider the performance of schemes in the many-user limit n → ∞.
In particular, we are interested in two limiting regimes, specifying how the degrees of freedom dof(n) should scale with the number of users n. In regime I the per-user rate is held constant; in regime II the sum-rate is kept constant, so each user's individual rate falls like 1/n.
• Regime I, where we hold the degrees of freedom constant as n → ∞.
That is, we want to communicate at fixed fraction of the single-user rate, as in the NGJV scheme. In this regime I, we take dof(n) = α for some α ∈ (0, 1/2]. (The NGJV scheme corresponds to α = 1/2.) • Regime II, where we allow the degrees of freedom to fall as the number of users increases, scaling like 1/n. That is, we want to communicate at a fixed multiple of the rate allowed by resource division schemes like TDMA. In regime II, we take dof(n) = β/n for some β ≥ 1. (TDMA corresponds to β = 1.) First, we consider how parent JAP-B schemes perform in the many-user limit.
Theorem 5.8. For regimes I and II, as above, and as n → ∞, we have the following results for the delay exponent T(n) of parent JAP-B schemes: • Regime I: Fix α ∈ (0, 1/2]. Then the delay exponent for dof(n) = α scales quadratically like • Regime II: Fix β > 1. Then the delay exponent for dof(n) = β/n scales linearly, in that T(n) = O(n), or more specifically, Proof. For regime I, we need dof = 1/(K + 1) ≥ α, so we take But the general bounds on delay exponents from Theorem 5.6 tell us that for fixed K we have T(n, K) ∼ 1 K n 2 . The result follows. For regime II, 1/(K + 1) = dof = β/n, so we need Hence Putting this into the bounds from Theorem 5.6 gives Rearranging gives the result.
Note that in regime I with α = 1/2, we get T(n) ∼ n 2 , the same as NGJV. We noted previously that child schemes produced by sharing the parent scheme JAP-B([m]) were particularly effective. The following theorem shows this.
Note that asymptotically, this means that in both regimes child schemes from JAP-B([m]) parent schemes are asymptotically more effective than any other parent scheme. This is because 4α 2 n 2 ≤ 1 1/α − 1 n 2 (with inequality unless α = 1/2, when no child scheme will achieve the desired degrees of freedom) and any constant is less than (β − 2)n for n sufficiently large. Note also that by the same argument as the above proof, sharing the NGJV parent scheme gives T(n) = 4α 2 n 2 in regime I, which is less good than sharing JAP-B([m]), but the same to first-order terms.

Conclusion
In the Secion 5.1, the questions we attempted to answer were: 1. Can we find a scheme that, like NGJV, achieves half the single-user rate, but at a lower time delay?
2. Can we find schemes that have lower time delays than NGJV, even at some cost to the rate achieved?
3. Specifically, which schemes from Question 2 perform well for situations where we have few users (n small)?
4. Specifically, which schemes from Question 2 perform well for situations where we have many users (n → ∞)?
5. What is a lower bound on the best time delay possible for any scheme achieving a given rate for a given number of users?
In answer to question 2, we defined the new sets of parent schemes JAP and the even more effective JAP-B, and also derived child schemes from them. We noted that these had lower time delays -and sometimes significantly lower -at the costs of some loss in rate (or equivalently degrees of freedom). We saw that the child schemes from JAP-B([n]) schemes were often particularly effective.
In answer to Questions 3 and 4, we explicitly found the best schemes JAP-B schemes for n ≤ 8, and analysed the asymptotic behaviour of our schemes as n → ∞.

Notes
This chapter is joint work with Oliver Johnson and Robert Piechocki, and is based on our paper [3].

Building the interference graph
In Section 2.6, we looked at resource division schemes such as resource division by time (Subsection 2.6.1). We noted that for a user to communicate without interference, it was necessary for all of the other users to stand idle. However, if not every receiver gets interference for every transmitter, than it might be possible for more than one user to communicate through the network at once.
For concreteness, consider the N-user finite field interference network with fixed fading, so For the moment, so that we can concentrate on the interference, we will assume that the noise Z is 0 with probability 1, so If we have for some i = j that h ji = h ij = 0, then both users i and j can communicate simultaneously and interference-free. (Recall that we use the word "user" to mean a transmitter-receiver pair. So we mean that if h ji = h ij = 0, then transmitter i can communicate to receiver i and simultaneously transmitter j can communicate to receiver j, both links without interference.) More generally, we can build the interference graph to show which users interfere with which.  Interference graph So two users i and j can communicate simultaneously and interference-free if they are not joined by an edge in the interference graph. More generally, any independent set of the interference graph can communicate at the same time.
(Recall that a set of vertices U ⊆ V is called independent if no edge in the graph joins one vertex in U to another.) Optimal use of such a resource division strategy requires operating using only maximal independent sets. In particular, the maximum degrees of freedom achievable by a resource division scheme is dof = α, where the interference number α of the graph is the size of the largest independent set. Given such a network, the users need to find out which other users they interfere with. Here is one method they could use to do so: Let each transmitter i choose a random nonzero message m i ∈ F q \ {0}. Then, for each of T timeslots, each transmitter i either sends m i or just sends the empty message 0. In other words, let x it = 1 denote that transmitter i communicates in timeslot t, and x it = 0 that she does not. Then each receiver j receives the signal For large q, the probability that y jt = 0 when at least one transmitter has x it = 1 is small -for the moment we neglect this. Then if y jt = 0, receiver j knows that h ji = 0 for all i with x it = 1; conversely, if y jt = 0, receiver j knows that h ji = 0 for at least one i with x it = 1.
Receiver j wants to discover which h ji are nonzero (but doesn't need to know their actual values) in as few tests T as possible -this T will depend on the number of users N, the number K of transmitters i for which h ji = 0, and the acceptable error probability . This is equivalent to the problem of group testing, which we will outline more fully in the next section.
Our model would be more accurate if we included a noise term Z that wasn't always 0 and if we did not neglect the possibility that signals cancel each other out. Thus we would like our group testing protocols to be robust to this noise and to still have a small probability of error . In this chapter, we investigate how a channel coding approach to group testing can help with this.
Similar problems in multiuser networks have also been studied from a group testing perspective. Berger and coauthors [66] and Capetanakis [67] studied this problem using a model where more than one interfering message results in a collision where all messages are lost (rather than our model where signals are superposed at the receiver). Zhang, Luo, and Guo [68] studied the Gaussian network, where low-interference links h ji ≈ 0 are assumed to be zero and those signals are treated as noise.
In the rest of this chapter, we outline the problem of group testing, and explore a new approach to it using techniques from channel coding (as outlined in Chapter 1).
We define for the first time group testing channels, which operate much like communications channels, and identify an important property where 'only defects matter' that allows us to prove a theorem on the number of tests needed for accurate group testing to be possible. We also give the first information theoretic bound on adaptive group testing, by drawing an analogy to channel coding with feedback.

Group testing: a very short introduction
The problem of group testing concerns detecting the defective members of a set of items through the means of pooled tests. (In our previous example, for receiver j, think of the 'defective items' as the interfering transmitters with h ji = 0.) Group testing as a subject dates back to the work of Dorfman [69] in 1940s studying practical ways of testing soldiers' blood for syphilis, and has received much attention from combinatorialists and probabilists since.
The setup is as follows: Suppose we have of a set N items, of which a subset K of size K is defective. To identify K, we could test each of the N items individually for defectiveness. However, when K is small compared to N, most of the tests will give negative results. A less wasteful method is to test pools of numerous items together at the same time. After a number T of such pooled tests, it should be possible to deduce which items were defective.
Let x it = 1 denote that item i is included in test t. In the so-called deterministic case, a test of n t := |{i : x it = 1}| items of which k t := |{i ∈ K : x it = 1}| are defective gives a negative result y t = 0 if no defects are tested (k t = 0) and a positive result if at least one defect is pooled into the test (k t ≥ 1).
After T tests, we make an estimate K of the defective set, with some average probability of error . We want to choose our tests in such a way that is small, while keeping T as low as possible.
Traditionally, this has been seen as a combinatorial problem: given N and K, one aims to find an N × T testing matrix X = (x it ) such that all ( N K ) possible defective sets K give a different sequence of test results y 1 , . . . , y T . This gives a zero error probability = 0, and one is interested in how small T can be made. (See, for example, the textbook of Du and Hwang [70] for more details on the combinatorial approach to group testing.) However, an alternative approach is to use random pools. That is, we set X it to be random 0s or 1s -typically, X it = 1 with some probability p IID across i and t, where p may depend on K and N. One then investigates how big T must be compared to N and K in order to keep the average error probability low.
Recent progress has been made on this channel coding approach by Atia and Saligrama [71], by comparing the problem to the classical problem of channel coding, first studied by Shannon [4]. (See Chapter 1 for more details on channel coding.) The two figures below show an interesting similarity between the two problems. Note that our goals are slightly different, though -in channel coding we wish to maximise the number of messages M for large blocklengths T; whereas in group testing we wish to minimise the number of tests T for a large number of items N. In single-user point-to-point channel coding, M messages are encoded into codewords (x m1 , . . . , x mT ) of length T. After being sent through some channel, the codewords are received as (y 1 , . . . , y T ), and the original message is estimated as m, with the hope that the average error probability will be small.
Shannon's celebrated channel coding theorem [4, Theorem 11] (see Theorem 1.11 of this thesis) tells us how large we can make M compared to T, while still being sure that the error probability stays small. Shannon's breakthrough was to study a random coding scheme, were the X mt are all IID according to some distribution X. One way to phrase the achievability part of Shannon's theorem -Shannon offered a similar phrasing as an alternative in his original paper [4, Theorem 12] -is the following: Theorem 6.2 (Shannon's channel coding theorem). Consider a communications channel (X , Y, p(y | x)). Let M * = M * (T, ) be the maximum number of messages that can be sent through the channel with blocklength T and error probability at most ∈ (0, 1). Then M * ≥ 2 T max X I(X:Y)+o(T) as T → ∞.
Atia and Saligrama [71, Theorem III.1] adapted Gallager's proof [10] of the achievability part of Shannon's channel coding theorem to give a similar result. This time, we're interested in how many tests T are required to keep the error probability arbitrarily low. Theorem 6.3. Consider group testing in the deterministic case.
Let T * = T * (N, K, ) be the minimum number of tests necessary to identify K defects among N items with error probability at most ∈ (0, 1). .
(It's worth noting that the term inside the maximisation depends only on the cardinality |L| of L, not on L itself.) In channel coding, the main interest is in finding the value of M * for different channels -the limit (Here, as elsewhere, we use f (x) ∼ g(x) to mean that f (x)/g(x) → 1.) Here, we will attempt to find to what range of group testing channels the result of Atia and Saligrama can be extended, and some bounds on T -and hence T * -for those channels. We also investigate further insights that channel coding can give to group testing.

Channels
In channel coding, many different types of communication can be modelled by using different channels. Recall from Definition 1.1 that a communication channel is defined by stating what inputs x ∈ X and outputs y ∈ Y the channel can have, and what the probability p(y | x)of each output is given each input.
We want to do the same for group testing. The input is already constrained: there are N items each of which can be in (x i = 1) or not in (x i = 0) the pool, so the input alphabet is {0, 1} N . So we must define the output alphabet and the probability function.
We will assume that in a testing pool there is no 'order' to the items, nor will any elements not placed in the pool affect the outcome of the test, nor can we distinguish between the items other than whether or not they are defective. Hence, the outcome can only depend on two things, the number of items in the test pool n, and the number of those items that are defective k.

Definition 6.4. A group testing channel consists of
• an output alphabet Y, • a probability transition function p(y | n, k) relating the number of items n and defectives k in a testing pool to the test outcome y.
The problem of group testing is then to come up with test designs that have a low error probability for as few tests as possible. Definition 6.5. A testing pool for N items consists of a vector x = (x i ) ∈ {0, 1} N , where x i = 1 denotes that item i is included in the pool and x i = 0 denotes that item i is not included in the pool. We define n := |{i : x i = 1}| to be the total number of items in the pool and k := |{i ∈ K : x i = 1}| to be the number of defective items in the pool.
A test design of T tests for N items consists of We can now describe the deterministic case discussed earlier as an example of a group testing channel under Defintion 6.4. Definition 6.6. The deterministic channel has output alphabet Y = {0, 1} and probability transition function Atia and Saligrama [71, Subsection II-C] also studied two ways in which error could be introduced into group testing, which they called the additive and dilution models. They showed that their main result (Theorem 6.3) also holds true for these two channels.
In the additive model, a negative pool can actually return a false positive result, with some fixed probability q. This could happen in our interference graph example from Section 6.1 if we included a noise term Z. This model can be recast as an example of a group testing channel. Definition 6.7. The addition channel with addition probability q > 0 has output alphabet Y = {0, 1} and probability transition function Atia and Saligrama [71, Table 1] calculated that for the addition channel, as K → ∞ and N → ∞, we have Using the work of Sejdinovic and Johnson [72,Theorem 6] we can improve this to by setting u = 0 and optimising α = 1 in their equation (22) and rearranging.
(Interestingly, this is discontinuous with the deterministic channel at q = 0.) The dilution model describes the case where a very small number of defective items in a testing pool might be 'drowned out' by the nondefective items. Specifically, any defective items in the test may each evade the test independently with some probability u, with the potential to cause false negative results. This could happen in our interference graph example from Section 6.1 if we did not neglect the possibility that superposed interfering signals can cancel each other out. Definition 6.8. The dilution channel with dilution probabilty u ≥ 0 has output alphabet Y = {0, 1} and probability transition function Atia and Saligrama [71, Table 1] calculated that for the addition channel we have Again, using the work of Sejdinovic and Johnson [72, Theorem 6] we can improve this to we do this by optimising α = 1/(1 − u) in their equation (24) and rearranging. In other words, the addition channel requires about e u ≈ 1 + u times as many tests as the deterministic channel, for small u. Sejdinovic and Johnson also considered a channel that combines the additive and dilutive noise models. Definition 6.9. The addition/dilution channel with addition probability q > 0 and dilution probabilty u ≥ 0 has output alphabet Y = {0, 1} and probability transition function Working on the unproven assumption that Atia and Saligrama's result (Theorem 6.3) also holds for the addition/dilution channel, Sejdinovic and Johnson [72, Theorem 3] prove a similar result for the addition/dilution channel. (Although note that Sejdinovic and Johnson [72, reference 1] were working from an earlier preprint of Atia and Saligrama's paper [71, version 2]. This had a different, and less rigorous, proof based on typical set decoding, rather than Gallager's maximum likelihood approach as in the most recent version [71, version 4].) Atia and Saligrama and Sejdinovic and Johnson defined their channels in terms of complicated Boolean sums and products of random vectors and matrices with the testing matrix X. But our definition in terms of probability transition functions makes the behaviour of such channels clearer, and should allow the proof of more universal theorems. It also makes it much easier to define new channels to model testing behaviour -and many other existing models can be reformulated as group testing channels. Definition 6.10. The erasure channel is a model that works like the deterministic channel, but fails to produce a result with some fixed erasure probability . That is, Y = {0, ?, 1} and The dilution threshold only gives a positive result if a sufficient proportion of the tested items are defective, above some threshold θ ∈ (0, 1). That is, Y = {0, 1} and The counting channel gives as the output the number of defective items in the set. That is, the probability transition function p(y | n, k) defined implicitly be the relation Y = k.
It's worth noting that group testing under the counting channel model is equivalent to 0-1 compressed sensing with sparsity exactly k. (A model equivalent to the count channel has previously been studied by Shapiro and Fine [73], Erdős and Rényi [74], and others -for more details see the textbook of Du and Hwang [70,Section 11.2].) The overflow channel gives as a result exactly how many defective items were in the test, up to some limit l. That is, Y = {0, 1, 2, . . . , l} and probability function definied implicitly by the relation Y = max{k, l}.
(When l = n, this is equivalent to the counting channel; when l = 1 this is equivalent to the deterministic channel; when l = 2 this is the message collision model of Capetanakis [67].) The symmetric channel gives a negative result if all items are nondefective, a positive result if all items are defective, and an uncertain result if there is a mixture of defective and nondefective items. That is, Y = {0, ?, 1} and relation (A model equivalent to the symmetric channel has previously been studied by Sobel, Kumar, and Blumenthal [75] and Hwang [76].) These are just a few examples -many more realistic error models for group testing can be formulated as channels, and perhaps wider use can be made of this new concept.

When only defects matter
Note that for many of the group testing channels we have mentioned -including all those studied by Atia and Saligrama and by Sejdinovic and Johnsonthe output depends only on k, the number of defects in the test, and not on n, the total number of items in the test. In other words, 'only defects matter', and the number of nondefects in the test is irrelevant. Definition 6.11. A channel (Y, p) whose probability function p(y | n, k) = p(y | k) is dependent only on k and not on n is said to have the only-defectsmatter property.
In the examples from Defintion 6.11 and earlier, the deterministic, addition, dilution, addition/dilution, erasure, counting, and overflow channels have the only-defects-matter property. The dilution threshold and symmetric channels do not have the only-defects-matter property Another way to state the only-defects-matter property is that for a channel where only defects matter, we can make the simplification P(Y | X) = P(Y | X K ).
Making this simplification is crucial to the proof of Atia and Saligrama [71, for example Section III.A]. Indeed, this is the only specific point about the deterministic, additive, and dilution channels that Atia and Saligrama use in their proof. Hence, we have the following: Theorem 6.12. Consider a group testing channel where only defects matter. Let T * = T * (N, K, ) be the minimum number of tests necessary to identify K defects among N items with error probability at most ∈ (0, 1). Then T * ≤ T + o(log N) as N → ∞, where The proof is the same as that of Atia and Saligrama's theorem [71, Theorem III.1]. We briefly outline the proof here.
Sketch proof. We need to analyse the error probability of a test design. To do this, we will analyse the probability our estimated defective set K of cardinality K overlaps with the true defective set K on a set L.
Given a set L There are ( N−K K−|L| ) such sets, and ( K |L| ) sets L of each possible cardinality. Using a technique similar to Gallager's proof of Shannon's coding theorem, we can bound the probability that we make an error in |L| places as Hence we require .
We need this to be true for every L ⊂ K, and can optimise the result over the test design parameter p.
Identifying the only-defects-matter property as the crucial factor for proving Theorem 6.12 means that Sejdinovic and Johnson's bound on T for the addition/dilution channel is now rigorously proven.
Whether Theorem 6.12 -or a similar theorem -holds for channels without the only-defects-matter property is an open problem.
Calculating, or finding good bounds for, the value of T or T * for the erasure, counting, and overflow channels is also an open problem.

Converse part and adaptive testing
Atia and Saligrama [71, Theorem IV.1] also provide a lower bound on the number of tests needed in group testing. The proof is along the lines of Shannon's converse to the channel coding theorem, and uses Fano's inequality. As before, the Atia-Saligrama proof in fact applies to all channels where only defects matter. Note that, unlike for channel coding, the bounds T and T do not coincide. Therefore, the exact number of tests needed for group testing to work is not known.
We now present a proof of the converse that is slightly simpler than Atia and Saligrama's. Our proof is based on theirs [71, Theorem IV.1], with some simplifications based on the standard proof of the converse of Shannon's coding theorem, as exposited by Cover and Thomas [6, Section 7.9].
Proof. Suppose a genie reveals to us some subset L ⊂ K of the defective set, leaving us to work out the remaining K − |L| defective items. Given L, let K be the random defective set chosen uniformly among the possible ( N−|L| K−|L| ) sets of size K of which L is a subset.
Then we have the following: where the final step is uses the data-processing inequality and the fact that only defects matter.
We can bound the mutual information term in (6.1) as = TI(X K\L : Y | X L ). (6.2) (Here, we write X Kt := (X it : i ∈ K) for fixed t.
But we can rewrite this mutual information as I(X K\L : Y | X L ) = I(X K\L : X L , Y) − I(X K\L : X L ) = I(X K\L : X L , Y), (6.3) since X K\L and X L are independent.
We can rearrange this to get to get the error probability arbitrarily low.
This has to be true for all L ⊂ K, and we can optimise over the test inclusion parameter p. This gives the result.
So far, we have been looking at nonadaptive group testing, where all the test pools are decided on ahead of time.
Instead, we could consider adaptive group testing where tests are performed sequentially, and the makeup of a testing pool can depend on the results of previous tests. That is, the x it are functions of the previous test outcomes (y 1 , y 2 , . . . , y t−1 ). Definition 6.14. An adaptive test design of T tests for N items consists of a sequence (x 1 , x 2 , . . . , x T ) of T testing pools, where the testing pool for the tth test x t = x t (y 1 , y 2 , . . . , y t−1 ) can depend on earlier test outcomes. This is analogous to channel coding with feedback, where the encoding function x t at time t can depend on previous channel outputs y 1 , y 2 , . . . , y t−1 .
As Shannon [77, page 15] showed, for discrete memoryless channels, feedback does not increase the channel capacity. (Although it can help in simplifying encoding and decoding [6,Section 7.12].) Due to the non-tightness of the bounds on testing in the nonadaptive case, we will not be able to show that adaptive group testing requires the same number of tests as nonadaptive testing, but we will be able to show that it obeys the same lower bound and requires no more tests than the nonadaptive case.
This is (as far as we are aware) the first application of information theoretic techniques to adaptive group testing. Theorem 6.15. Let T * N A and T * A (dependent on N,K, and ) be the minimum number of tests necessary to identify K defects among N items with error probability at most ∈ (0, 1) for nonadaptive and adaptive group testing respectively. Then, as N → ∞, we have the inequalities where T and T are as in Theorems 6.3 and 6.13.
Proof. The third inequality was proven in Theorem 6.3. The second inequality is trivial, as nonadaptive group testing is merely a special case of adaptive group testing where the tester chooses to ignore the information of previous test results.
To prove the first inequality, we adapt the proof of Theorem 6.13, and Shannon's proof that feedback fails to improve channel capacity [77,Theorem 6], as exposited by Cover and Thomas [6, Theorem 7.12.1].
We begin exactly the same way as the proof of Theorem 6.13, to get log N − |L| K − |L| ≤ 1 + log N − |L| K − |L| + I(K : K | L). (6.4) We again use the data processing inequality (but in a slightly different way) and the only-defects-matter property on the mutual information term in (6.4), to write where (6.5) is because, conditional on X Kt , we know that Y t is independent of previous Ys and the defective set K.
We can now pick back up with the proof of Theorem 6.13, two lines above (6.2), to complete the proof.
It is tempting to wonder if in fact non-adaptive and adaptive group testing require exactly the same number of tests T * A = T * N A . This would be in contrast to results for the deterministic model in the zero-error case, where it is known that adaptive group testing can be performed in strictly fewer tests than nonadaptive (in the K → ∞, N → ∞ regime) [70, page 139].
Similarly, Shannon showed that feedback for channel coding does help in the zero-error case, but not the arbitrarily-small-error case [77].

Further work
The investigation of applying information theoretic ideas to group testing is at a very early stage and there are many open questions.
Can we find an analogue of Theorem 6.12 where nondefects also matter?
That is, can we drop the only-defects-matter property. The proof of Theorem 6.12 relies on the fact that, given K ∩ K =: L, the random variables P(Y | X, K defective) and P(Y | X, K defective) are conditionally independent. While this is no longer true when nondefects matter too, they are still conditionally independent given L and the total number of items n in the test. Perhaps this promises a way forwards.
What is T * for different channels? Is there a reliable method to calculate, exactly or approximately, T * for different channels. Is there an easy way to do so? What are the minimising choices of p?
Can we close the gap between T and T to tighten our bounds?
Does nonadaptive group testing require more tests than adaptive? That is, does T * A = T * N A asymptotically.
The wider view: What other information-theoretic techniques can be useful? Sejdinovic and Johnson [72] have tried using message-passing decoding algorithms for computationally feasible defective set detection. Cheraghchi and coauthors [78] have used information theoretic techniques to study group testing on graphs. What else is there to try?
That's just a few brief suggestions.

Notes
This chapter has benefited from discussions with Oliver Johnson, Dino Sejdinovic, and Robert Piechocki. Group testing was first studied by Dorfman [69] in the context of testing soldiers' blood for syphilis.
The information theoretic approach to group testing is due to Atia and Saligrama [71]. A recent paper of Sejdinovic and Johnson was also useful [72].
The textbook of Du and Hwang [70] was useful for material on group testing. The textbook of Cover and Thomas [6] was useful for material on channel coding.

Conclusions and further work
In this thesis, we've examined a number of different ways of combating interference in wireless networks.
• In Chapter 3 we saw how the simple interference-as-noise technique can be effective over short hops in well-structured networks.
• In Chapter 4, we saw how interference alignment can give tight bounds on the performance of large random networks.
• In Chapter 5, we examined the tradeoff between delay and communication rate when using ergodic interference alignment.
• In Chapter 6, we examined how group testing can help with network performance, and how channel coding techniques can help with group testing.
As we've gone through, we have left a number of pointers to open questions and further work (in particular, see Sections 3.4, 4.6, 5.6, and 6.6). We now have the opportunity to take a brief look at the wider picture.
• While interference alignment has been an important theoretical breakthrough, it has had few practical benefits to date. The work in Chapter 5 of this thesis on delay-rate tradeoff is a step in the right direction, but more work is needed. How can we reduce the complexity of schemes? Can we reduce the amount of channel state information required? Can we reduce blocklengths further? Are the schemes robust to errors in channel estimation?
• There is no Shannon's channel coding theorem for networks. That is, there is no general result that tells one how to calculate the capacity region (or even just the sum-capacity) of a network. (The best current result is the cutset bound of Cover and Thomas [6, Theorem 15.10.1].) Even a result for the Gaussian case seems far off -Jafar refers to a result in the Gaussian case for only interference networks as "the holy grail of network information theory" [27, page 1].
• Most capacity theorems for networks -including those in this thesisare nonconstructive. That is, no explicit codes are given. Are some coding schemes particularly well suited to interference alignment schemes, or can standard codes (like low-density parity-check codes) be adapted to this new area?
• Theorems about sum-capacity (such as ours in Chapter 4) do not give everything we want to know about a network. After all, a network operating solely at its optimal sum-rate may provide very poor performance for some unfortunate users. Concepts of fairness and cooperation also need to be taken into account.
• As wireless devices become ever more ubiquitous, many engineering problems in this area become ever more severe. Networks must be set up 'ad hoc' with little prior knowledge (the example in Section 6.1 shows one way of approaching this); also, interference will become a much bigger problem, and 'green' technologies with low power consumption will be important.
• Work on the connection between group testing and channel coding is at a very early stage -in Section 6.6 we listed a number of future directions for research. Are other mathematical problems that involve inference about unknown quantities approachable from an information theoretic point of view? How far can Shannon's work at a 1940s telephone company take us?