Hypothesis testing problems for circular data are formulated, where observations take values on the unit circle and may contain a hidden, phase-coherent structure. Under the null, the data are independent uniform on the unit circle; under the alternative, either (i) a planted subset of size K concentrates around an unknown phase (the flat setting), or (ii) a planted community of size k induces coherence among the edges of a complete graph (the community setting). In each of the two settings, two circular signal distributions are considered: a hard-cluster distribution, where correlated planted observations lie in an arc of known length and unknown location, and a von Mises distribution, where correlated planted observations follow a von Mises distribution with a common unknown location parameter. For each of the four resulting models, nearly matching necessary and sufficient conditions are derived (up to constants and occasional logarithmic factors) for detectability, thereby establishing information-theoretic phase transitions.

This work studies fundamental limits for recovering the underlying correspondence among multiple correlated random graphs. We identify a necessary condition for any algorithm to correctly match all nodes across all graphs, and propose two algorithms for which the same condition is also sufficient. The first algorithm employs global information to simultaneously match all the graphs, whereas the second algorithm first partially matches the graphs pairwise and then combines the partial matchings by transitivity. Both algorithms work down to the information theoretic threshold. Our analysis reveals a scenario where exact matching between two graphs alone is impossible, but leveraging more than two graphs allows exact matching among all the graphs. Along the way, we derive independent results about the k-core of Erdős-Rényi graphs. Deferred proofs are available in the preprint, arXiv 2405.12293 [1].

This paper studies the hypothesis testing problem to determine whether$m \geq 2$unlabeled graphs with Gaussian edge weights are correlated under a latent permutation. Previously, a sharp detection threshold for the correlation parameter$\rho$was established by Wu, Xu and Yu [1] for this problem when$m= 2$. Presently, their result is leveraged to derive necessary and sufficient conditions for general$m$. In doing so, an interval for$\rho$is uncovered for which detection is impossible using 2 graphs alone but becomes possible with$m>2$graphs.

The optimal receiver operating characteristic (ROC) curve, giving the maximum probability of detection as a function of the probability of false alarm, is a key information-theoretic indicator of the difficulty of a binary hypothesis testing problem (BHT). It is well known that the optimal ROC curve for a given BHT, corresponding to the likelihood ratio test, is determined by the probability distribution of the observed data under each of the two hypotheses. In some cases, these two distributions may be unknown or computationally intractable, but independent samples of the likelihood ratio can be observed. This raises the problem of estimating the optimal ROC for a BHT from such samples. The maximum likelihood estimator of the optimal ROC curve is derived, and it is shown to converge almost surely to the true optimal ROC curve in the Lévy metric, as the number of observations tends to infinity. Finite sample size bounds are obtained for three other estimators: the classical empirical estimator, based on estimating the two types of error probabilities from two separate sets of samples, and two variations of the maximum likelihood estimator called the split estimator and fused estimator, respectively. The maximum likelihood estimator is observed in simulation experiments to be considerably more accurate than the empirical estimator, especially when the number of samples obtained under one of the two hypotheses is small. The area under the maximum likelihood estimator is derived; it is a consistent estimator of the area under the true optimal ROC curve.

A payment channel network is a blockchain-based overlay mechanism that allows parties to transact more efficiently than directly using the blockchain. These networks are composed of payment channels that carry transactions between pairs of users. Due to its design, a payment channel cannot sustain a net flow of money in either direction indefinitely. Therefore, a payment channel network cannot serve transaction requests arbitrarily over a long period of time. We introduceDEBT control, a joint routing and flow-control protocol that guides a payment channel network towards an optimal operating state for any steady-state demand. In this protocol, each channel sets a price for routing transactions through it. Transacting users make flow-control and routing decisions by responding to these prices. A channel updates its price based on the net flow of money through it. We develop the protocol by formulating a network utility maximization problem and solving its dual through gradient descent. We provide convergence guarantees for the protocol and also illustrate its behavior through simulations.

Two models are introduced to study the problem of matching two correlated graphs when some of the nodes are corrupt. In the weak model, a random subset of nodes in one or both graphs can interact randomly with their network. For this model, it is shown that no estimator can correctly recover a positive fraction of the corrupt nodes. Necessary conditions for any estimator to correctly identify and match all the uncorrupt nodes are derived, and it is shown that these conditions are also sufficient for the k-core estimator. In the strong model, an adversarially selected subset of nodes in one or both graphs can interact arbitrarily with their network. For this model, detection of corrupt nodes is impossible. Even so, we show that if only one of the networks is compromised, then under appropriate conditions, the maximum overlap estimator can correctly match a positive fraction of nodes albeit without explicitly identifying them.

The optimal receiver operating characteristic (ROC) curve, giving the maximum probability of detection as a function of the probability of false alarm, is a key information-theoretic indicator of the difficulty of a binary hypothesis testing problem (BHT). It is well known that the optimal ROC curve for a given BHT, corresponding to the likelihood ratio test, is theoretically determined by the probability distribution of the observed data under each of the two hypotheses. In some cases, these two distributions may be unknown or computationally intractable, but independent samples of the likelihood ratio can be observed. This raises the problem of estimating the optimal ROC for a BHT from such samples. The maximum likelihood estimator of the optimal ROC curve is derived, and it is shown to converge to the true optimal ROC curve in the Lévy metric, as the number of observations tends to infinity. A classical empirical estimator, based on estimating the two types of error probabilities from two separate sets of samples, is also considered. The maximum likelihood estimator is observed in simulation experiments to be considerably more accurate than the empirical estimator, especially when the number of samples obtained under one of the two hypotheses is small. The area under the maximum likelihood estimator is derived; it is a consistent estimator of the true area under the optimal ROC curve.

Recovery of the causal structure of dynamic networks from noisy measurements has long been a problem of intense interest across many areas of science and engineering. Many algorithms have been proposed, but there is no work that compares the performance of the algorithms to converse bounds in a non-asymptotic setting. As a step to address this problem, this paper gives lower bounds on the error probability for causal network support recovery in a linear Gaussian setting. The bounds are based on the use of the Bhattacharyya coefficient for binary hypothesis testing problems with mixture probability distributions. Comparison of the bounds and the performance achieved by two representative recovery algorithms are given for sparse random networks based on the Erdős-Rényi model.

A message passing algorithm is derived for recovering communities within a graph generated by a variation of the Barabási-Albert preferential attachment model. The estimator is assumed to know the arrival times, or order of attachment, of the vertices. The derivation of the algorithm is based on belief propagation under an independence assumption. Two precursors to the message passing algorithm are analyzed: the first is a degree thresholding (DT) algorithm and the second is an algorithm based on the arrival times of the children (C) of a given vertex, where the children of a given vertex are the vertices that attached to it. Comparison of the performance of the algorithms shows it is beneficial to know the arrival times, not just the number, of the children. The probability of correct classification of a vertex is asymptotically determined by the fraction of vertices arriving before it. Two extensions of Algorithm C are given: the first is based on joint likelihood of the children of a fixed set of vertices; it can sometimes be used to seed the message passing algorithm. The second is the message passing algorithm. Simulation results are given.

A message passing algorithm is derived for recovering a dense subgraph within a graph generated by a variation of the Barabasi-Albert preferential attachment model. The estimator is assumed to know the order of attachment, of the vertices. The derivation of the algorithm is based on belief propagation under an independence assumption. Two precursors to the message passing algorithm are analyzed: the first is a degree thresholding (DT) algorithm and the second is an algorithm based on the arrival times of the children (C) of a given vertex, where the children of a given vertex are the vertices that attached to it. Algorithm C significantly outperforms DT, showing it is beneficial to know the arrival times of the children, beyond simply knowing the number of them. For fixed fraction of vertices in the community, fixed number of new edges per arriving vertex, and fixed affinity between vertices in the community, the probability of error for recovering the label of a vertex is found as a function of the time of attachment, for either algorithm DT or C, in the large graph limit. By averaging over the time of attachment, the limit in probability of the fraction of label errors made over all vertices is identified, for either of the algorithms DT or C. An extended version of this paper is at arXiv 1801.06818, which also includes message passing for two symmetric communities.

We study the problem of recovering a hidden community of cardinality K from an n × n symmetric data matrix A, where for distinct indices i, j, Aij~ P if i, j both belong to the community and Aij~ Q otherwise, for two known probability distributions P and Q depending on n. If P = Bern(p) and Q = Bern(q) with p q, it reduces to the problem of finding a densely connected K-subgraph planted in a large Erdös-Rényi graph; if P = )V (μ, 1) and Q = )V (0, 1) with μ > 0, it corresponds to the problem of locating a K × K principal submatrix of elevated means in a large Gaussian random matrix. We focus on two types of asymptotic recovery guarantees as n → ∞: 1) weak recovery: expected number of classification errors is o(K) and 2) exact recovery: probability of classifying all indices correctly converges to one. Under mild assumptions on P and Q, and allowing the community size to scale sublinearly with n, we derive a set of sufficient conditions and a set of necessary conditions for recovery, which are asymptotically tight with sharp constants. The results hold, in particular, for the Gaussian case, and for the case of bounded log likelihood ratio, including the Bernoulli case whenever (p/q) and (1 - p)/(1 - q) are bounded away from zero and infinity. Previous work has shown that if weak recovery is achievable; then, exact recovery is achievable in linear additional time by a simple voting procedure. We provide a converse, showing the condition for the voting procedure to succeed is almost necessary for exact recovery.

We study a semidefinite programming (SDP) relaxation of the maximum likelihood estimation for exactly recovering a hidden community of cardinality K from an n \times n symmetric data matrix A, where for distinct indices i,j, A_ij ∼P if i, j are both in the community and A_ij ∼Q otherwise, for two known probability distributions P and Q. We identify a sufficient condition and a necessary condition for the success of SDP for the general model. For both the Bernoulli case (P=\rm Bern(p) and Q=\rm Bern(q) with p>q) and the Gaussian case (P=\mathcalN(μ,1) and Q=\mathcalN(0,1) with μ>0), which correspond to the problem of planted dense subgraph recovery and submatrix localization respectively, the general results lead to the following findings: (1) If K=ω( n /\log n), SDP attains the information-theoretic recovery limits with sharp constants; (2) If K=Θ(n/\log n), SDP is order-wise optimal, but strictly suboptimal by a constant factor; (3) If K=o(n/\log n) and K \to ∞, SDP is order-wise suboptimal. The same critical scaling for K is found to hold, up to constant factors, for the performance of SDP on the stochastic block model of n vertices partitioned into multiple communities of equal size K. A key ingredient in the proof of the necessary condition is a construction of a primal feasible solution based on random perturbation of the true cluster matrix.

We study the problem of recovering a hidden community of cardinality K from an n × n symmetric data matrix A, where for distinct indices i; j, Aij~ P if i; j both belong to the community and Aij~ Q otherwise, for two known probability distributions P and Q depending on n. We focus on two types of asymptotic recovery guarantees as n → ∞: (1) weak recovery: expected number of classification errors is o(K); (2) exact recovery: probability of classifying all indices correctly converges to one. Under mild assumptions on P and Q, and allowing the community size to scale sublinearly with n, we derive a set of sufficient conditions and a set of necessary conditions for recovery, which are asymptotically tight with sharp constants. The results hold in particular for the Gaussian case (P = N(μ, 1) and Q = N(0; 1)), and for the case of bounded log likelihood ratio, including the Bernoulli case (P = Bern(p) and Q = Bern(q)) whenever p/q and 1-p/1-q are bounded away from zero and infinity. An important algorithmic implication is that, whenever exact recovery is information theoretically possible, any algorithm that provides weak recovery when the community size is concentrated near K can be upgraded to achieve exact recovery in linear additional time by a simple voting procedure.

The binary symmetric stochastic block model deals with a random graph of n vertices partitioned into two equal-sized clusters, such that each pair of vertices is independently connected with probability p within clusters and q across clusters. In the asymptotic regime of p = a log n/n and q = b log n/n for fixed a, b, and n → ∞, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to n.

Resolving a conjecture of Abbe, Bandeira, and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model (SBM) of two equal-sized clusters. The same was shown for the case of a single cluster and outliers. Extending the proof techniques, in this paper, it is shown that SDP relaxations also achieve the sharp recovery threshold in the following cases: 1) binary SBM with two clusters of sizes proportional to network size but not necessarily equal; 2) SBM with a fixed number of equal-sized clusters; and 3) binary censored block model with the background graph being Erdös-Rényi. Furthermore, a sufficient condition is given for an SDP procedure to achieve exact recovery for the general case of a fixed number of clusters plus outliers. These results demonstrate the versatility of SDP relaxation as a simple, general purpose, computationally feasible methodology for community detection.

This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph \calG(N,q), where the edge probability within the community exceeds q by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computational complexity of detecting the community exhibits the following phase transition phenomenon: As the graph size N grows and the graph becomes sparser according to q=N^-α, there exists a critical value of α= \frac23, below which there exists a computationally intensive procedure that can detect far smaller communities than any computationally efficient procedure, and above which a linear-time procedure is statistically optimal. The results also lead to the average-case hardness results for recovering the dense community and approximating the densest K-subgraph.

The binary symmetric stochastic block model deals with a random graph of n vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability p within clusters and q across clusters. In the asymptotic regime of p = a log n/n and q = b log n/n for fixed a, b and n → ∞, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. [1]. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to n.

A recurring theme in the design of control schemes for computer communication networks has been to identify the drift of critical quantities such as queue lengths, and then devise control strategies that close the loop. A useful tool for the performance analysis of such strategies are bounds on deviations from the expected trajectory. This talk identifies an incomplete list of such tools that have been used in a broad class of applications, for both stochastic and deterministically constrained models of load.

Given a set of pairwise comparisons, the classical ranking problem computes a single ranking that best represents the preferences of all users. In this paper, we study the problem of inferring individual preferences, arising in the context of making personalized recommendations. In particular, we assume users form clusters; users of the same cluster provide similar pairwise comparisons for the items according to the Bradley-Terry model. We propose an efficient algorithm to estimate the preference for each user: first, compute the net-win vector for each user using the comparisons; second, cluster the users based on the net-win vectors; third, estimate a single preference for each cluster separately. We show that the net-win vectors are much less noisy than the high dimensional vectors of pairwise comparisons, therefore our algorithm can cluster the users reliably. Moreover, we show that, when a cluster is only approximately correct, the maximum likelihood estimation for the Bradley-Terry model is still close to the true preference.

We study the content placement problem for cache delivery video-on-demand systems under static random network topologies with fixed heavy-tailed video demand. The performance measure is the amount of server load; we wish to minimize the total download rate for all users from the server and maximize the rate from caches. Our approach reduces the analysis for multiple videos to consideration of decoupled systems with a single video each. For each placement policy, insights gained from the single video analysis carry back to the original multiple video content placement problem. Finally, we introduce a hybrid placement technique that achieves near optimal performance with low complexity.

In standard clustering problems, data points are represented by vectors, and by stacking them together, one forms a data matrix with row or column cluster structure. In this paper, we consider a class of binary matrices, arising in many applications, which exhibit both row and column cluster structure, and our goal is to exactly recover the underlying row and column clusters by observing only a small fraction of noisy entries. We first derive a lower bound on the minimum number of observations needed for exact cluster recovery. Then, we study three algorithms with different running time and compare the number of observations needed by them for successful cluster recovery. Our analytical results show smooth time-data trade offs: one can gradually reduce the computational complexity when increasingly more observations are available.

A supermarket game is considered with N FCFS queues with unit exponential service rate and global Poisson arrival rate Nλ. Upon arrival each customer chooses a number of queues to be sampled uniformly at random and joins the least loaded sampled queue. Customers are assumed to have cost for both waiting and sampling, and they want to minimize their own expected total cost. We study the supermarket game in a mean field model that corresponds to the limit as N converges to infinity in the sense that (i) for a fixed symmetric customer strategy, the joint equilibrium distribution of any fixed number of queues converges as N → ∞ to a product distribution determined by the mean field model and (ii) a Nash equilibrium for the mean field model is an e-Nash equilibrium for the finite N model with N sufficiently large. It is shown that there always exists a Nash equilibrium for λ2≤ 1/2. Furthermore, we find that the action of sampling more queues by some customers has a positive externality on the other customers.

This paper focuses on the stationary portion of file download in an unstructured peer-to-peer network, which typically follows for many hours after a flash crowd initiation. The model includes the case that peers can have some pieces at the time of arrival. The contribution of this paper is to identify how much help is needed from the seeds, either fixed seeds or peer seeds (which are peers remaining in the system after obtaining a complete collection), to stabilize the system. The dominant cause for instability is the missing piece syndrome, whereby one piece becomes very rare in the network. It is shown that stability can be achieved with only a small amount of help from peer seeds-even with very little help from a fixed seed, peers need dwell as peer seeds on average only long enough to upload one additional piece. The region of stability is insensitive to the piece selection policy. Network coding can substantially increase the region of stability in case a portion of the new peers arrive with randomly coded pieces.

Peer-to-peer (P2P) communication in networks for file distribution and other applications is a powerful multiplier of network utility, due to its ability to exploit parallelism in a distributed way. As new variations are engineered, to provide less impact on service providers and to provide better quality of service, it is important to have a theoretical underpinning, to weigh the effectiveness of various methods for enhancing the service. This paper focuses on the stationary portion of file download in an unstructured P2P network, which typically follows for many hours after a flash crowd initiation. The contribution of the paper is to identify how much help is needed from the seeds, either fixed seeds or peers dwelling in the system after obtaining the complete file, to stabilize the system. It is shown that dominant cause for instability is the missing piece syndrome, whereby one piece becomes very rare in the network. It is shown that very little dwell time is necessary--even if there is very little help from a fixed seed, peers need to dwell on average no longer than it takes to upload one additional piece, after they have obtained a complete collection.

Typical protocols for peer-to-peer file sharing over the Internet divide files to be shared into pieces. New peers strive to obtain a complete collection of pieces from other peers and from a seed. In this paper we identify a problem that can occur if the seeding rate is not large enough. The problem is that, even if the statistics of the system are symmetric in the pieces, there can be symmetry breaking, with one piece becoming very rare. If peers depart after obtaining a complete collection, they can tend to leave before helping other peers receive the rare piece.

The calculus of deterministic constraints on service and traffic streams offers a rich language to specify service guarantees. In particular, the service curve earliest deadline first (SCED) algorithm has an associated feasibility test given by linear constraints. Users sending streams of data through the server may have differing needs for delay and throughput.We suggest a way based on utility function maximization, subject to the linear constraints of the SCED algorithm, for allocation of service. In addition, a generalization of the SCED algorithm is given which does not require that the deadline sequences within streams be monotone nondecreasing.

Discrete-time Rayleigh-fading single-input single-output (SISO) and multiple-input multiple-output (MIMO) channels are considered, with no channel state information at the transmitter or the receiver. The fading is assumed to be stationary and correlated in time, but independent from antenna to antenna. Peak-power and average-power constraints are imposed on the transmit antennas. For MIMO channels, these constraints are either imposed on the sum over antennas, or on each individual antenna. For SISO channels and MIMO channels with sum power constraints, the asymptotic capacity as the peak signal-to-noise ratio (SNR) goes to zero is identified; for MIMO channels with individual power constraints, this asymptotic capacity is obtained for a class of channels called transmit separable channels. The results for MIMO channels with individual power constraints are carried over to SISO channels with delay spread (i.e., frequency-selective fading).

This paper explores optimization of paging and registration policies in cellular networks. Motion is modeled as a discrete-time Markov process, and minimization of the discounted, infinite-horizon average cost is addressed. The structure of jointly optimal paging and registration policies is investigated through the use of dynamic programming for partially observed Markov processes. It is shown that there exist policies with a certain simple form that are jointly optimal. An iterative algorithm for policies with the simple form is proposed and investigated. The algorithm alternates between paging policy optimization, and registration policy optimization. It finds a pair of individually optimal policies. Majorization theory and Riesz's rearrangement inequality are used to show that jointly optimal paging and registration policies are given for symmetric or Gaussian random walk models by the nearest-location-first paging policy and distance threshold registration policies.

This paper investigates the dissemination of multiple pieces of information in large networks where users contact each other in a random uncoordinated manner, and users upload one piece per unit time. The underlying motivation is the design and analysis of piece selection protocols for peer-to-peer networks which disseminate files by dividing them into pieces. We first investigate one-sided protocols, where piece selection is based on the states of either the transmitter or the receiver. We show that any such protocol relying only on pushes, or alternatively only on pulls, will be inefficient in disseminating all pieces to all users. We propose a hybrid one-sided piece selection protocol -INTERLEAVE -and show that by using both pushes and pulls it disseminates k pieces from a single source to n users in 10(k + log n) time, while obeying the constraint that each user can upload at most one piece in one unit of time. An optimal, unrealistic centralized protocol would take k + log2n time in this setting. Moreover, efficient dissemination is also possible if the source implements forward erasure coding, and users push the latest-released coded pieces (but do not pull). We also investigate two-sided protocols where piece selection is based on the states of both the trasmitter and the receiver. We show that it is possible to disseminate n pieces to n users in + O(log n) time, starting from an initial state where each user has a unique piece.

Discrete-time Rayleigh fading multiple-input multiple-output (MIMO) channels are considered, with no channel state information at the transmitter and receiver. The fading is assumed to be correlated in time and independent from antenna to antenna. Peak and average transmit power constraints are imposed, either on the sum over antennas, or on each individual antenna. In both cases, an upper bound and an asymptotic lower bound, as the signal-to-noise ratio approaches zero, on the channel capacity are presented. The limit of normalized capacity is identified under the sum power constraints, and, for a subclass of channels, for individual power constraints. These results carry over to a SISO channel with delay spread (i.e. frequency selective fading).

rdquoThe VCG-Kelly mechanism is proposed, which is obtained by composing the communication efficient, one- dimensional signaling idea of Kelly with the VCG mechanism, providing efficient allocation for strategic buyers at Nash equilibrium points. It is shown that the revenue to the seller can be maximized or minimized using a particular one-dimensional family of surrogate valuation functions.

This paper investigates the dissemination of multiple pieces of information in large networks where users contact each other in a random uncoordinated manner, and users upload one piece per unit time. The underlying motivation is the design and analysis of piece selection protocols for peer-to-peer networks which disseminate files by dividing them into pieces. We first investigate one-sided protocols, where piece selection is based on the states of either the transmitter or the receiver. We show that any such protocol relying only on pushes, or alternatively only on pulls, is inefficient in disseminating all pieces to all users. We propose a hybrid one-sided piece selection protocol-INTERLEAVE-and show that by using both pushes and pulls it disseminates k pieces from a single source to n users in 9(k + log n) time, while obeying the constraint that each user can upload at most one piece in one unit of time, with high probability for large n. An optimal, unrealistic, centralized protocol would take k + log2n time in this setting. For a soft upload constraint, the finishing time of INTERLEAVE is, with high probability, at most 3.2(k + log n). Moreover, efficient dissemination is also possible if the source implements forward erasure coding, and users push the latest released coded pieces (but do not pull). We also investigate two-sided protocols where piece selection is based on the states of both the transmitter and the receiver. We show that it is possible to disseminate n pieces to n users in n + O(log n) time, starting from an initial state where each user has a unique piece.

Bit-error probability and mutual information rate have both been used as performance criteria for space-time codes for wireless communication. We use mutual information as the performance criterion because it determines the possible rate of communication when using an outer code. In this context, linear dispersion codes, first proposed by Hassibi and Hochwald, are appealing because of the high mutual information they provide, as well as their simplicity. Because complexity increases with the number of symbols, it may be sensible in some settings to fix the number of symbols sent per data bit. In the dissertation of Y. Jiang, it was conjectured that among linear dispersion codes with independent, binary symbols, orthogonal space-time codes are optimal in the following sense: they maximize mutual information subject to an average power constraint on each symbol. We prove the conjecture for a fixed number of real symbols with arbitrary distributions

Flat-fading channels that are correlated in time are considered under peak and average power constraints. For discrete-time channels, a new upper bound on the capacity per unit time is derived. A low SNR analysis of a full-scattering vector channel is used to derive a complimentary lower bound. Together, these bounds allow us to identify the exact scaling of channel capacity for a fixed peak to average ratio, as the average power converges to zero. The upper bound is also asymptotically tight as the average power converges to zero for a fixed peak power. For a continuous time infinite bandwidth channel, Viterbi identified the capacity for M-FSK modulation. Recently, Zhang and Laneman showed that the capacity can be achieved with non-bursty signaling (QPSK). An additional contribution of this paper is to obtain similar results under peak and average power constraints

Caire, Taricco, and Biglieri presented a detailed analysis of bit-interleaved coded modulation (BICM), a simple and popular technique used to improve system performance, especially in the context of fading channels. They derived an upper bound to the probability of error, called the expurgated bound. In this correspondence, the proof of the expurgated bound is shown to be flawed. A new upper bound is also derived. It is not known whether the original expurgated bound is valid for the important special case of square QAM with Gray labeling, but the new bound is very close to, and slightly tighter than, the original bound for a numerical example.

This paper investigates multiuser diversity in the context of cellular networks, with emphasis on the gains that can be achieved by adaptively inducing fluctuations in the environment. In a cellular system that at any time schedules for service the user with the best channel at that time, the expected service rate increases with the variability of the channel. Controlling the fluctuations using available feedback can further increase the expected service rate. This paper proposes a scheme for controlling fluctuations using only the feedback required to exploit multiuser diversity. Fluctuations are induced by introducing at the base station another transmit antenna that sends out the same signal but at a different phase from the first one, and then adaptively varying the phase difference. The performance of the scheme (for the same total transmitted power) is evaluated when the users are infinitely back-logged or have finite queues, and when the channels are Rayleigh or Ricean distributed. Fairness issues and performance of the scheme under an additional fairness mechanism are also investigated in the context of users with finite queues. In all scenarios the performance is better when fluctuations are adaptively induced than when the fluctuations are randomly induced or not induced at all

A central fact in the theory of optimal auction design is that the seller of a single object in an auction with n bidders, having independent, random valuations, typically cannot extract the full maximum value of the object from the buyers. We show that if the seller has access to a single bit of information, even if noisy, then the seller can extract full value. The work is meant to explore the use of information measures in mechanism design problems

A discrete-time single-user channel with temporally correlated Rayleigh fading is considered. Neither the transmitter nor the receiver has channel side information (CSI), and both peak and average power constraints are placed on the inputs. Two lower bounds to the capacity are presented. One is motivated by the technique of decision feedback decoding. The other is related to the information rate with side information present, minus a penalty term to account for the information about the channel that is learned at the receiver. The second lower bound is a slight variation of a bound of Shamai and Marzetta. The bounds are compared numerically to two upper bounds for a channel with Gauss Markov Rayleigh fading. One upper bound is the capacity for complete CSI, with the peak constraint ignored, and the other is based on the capacity per unit energy. In general, the gap between the upper and lower bounds depends on the channel memory, but is quite small for low SNR

A discrete-time single-user scalar channel with temporally correlated Rayleigh fading is analyzed. There is no side information at the transmitter or the receiver. A simple expression is given for the capacity per unit energy, in the presence of a peak constraint. The simple formula of Verdu/spl acute/ for capacity per unit cost is adapted to a channel with memory, and is used in the proof. In addition to bounding the capacity of a channel with correlated fading, the result gives some insight into the relationship between the correlation in the fading process and the channel capacity. The results are extended to a channel with side information, showing that the capacity per unit energy is one nat per joule, independently of the peak power constraint. A continuous-time version of the model is also considered. The capacity per unit energy subject to a peak constraint (but no bandwidth constraint) is given by an expression similar to that for discrete time, and is evaluated for Gauss-Markov and Clarke fading channels.

It is well known that independent and identically distributed Gaussian inputs, scaled appropriately based on the signal-to-noise ratio (SNR), achieve capacity on the additive white Gaussian noise (AWGN) channel at all values of SNR. In this correspondence, we consider the question of whether such good input distributions exist for frequency-nonselective Rayleigh-fading channels, assuming that neither the transmitter nor the receiver has a priori knowledge of the fading coefficients. In this noncoherent regime, for a Gauss-Markov model of the fading channel, we obtain explicit mutual information bounds for the Gaussian input distribution. The fact that Gaussian input generates bounded mutual information motivates the search for better choices of fixed input distributions for high-rate transmission over rapidly varying channels. Necessary and sufficient conditions are derived for characterizing such distributions for the worst case scenario of memoryless fading, using the criterion that the mutual information is unbounded as the SNR gets large. Examples of both discrete and continuous distributions that satisfy these conditions are given. A family of fixed input distributions with mutual information growth rate of O((loglogSNR)/sup 1-u/), u>0 are constructed. It is also proved that there does not exist a single fixed-input distribution that achieves the optimal mutual information growth rate of loglogSNR.

This paper explores optimization of paging and registration policies in cellular networks. Motion is modeled as a discrete-time Markov process, and minimization of the discounted, infinite-horizon average cost is addressed. The structure of jointly optimal paging and registration policies is investigated through the use of dynamic programming for partially observed processes. It is shown that there exist policies with a certain simple structure that are jointly optimal, though the dynamic programming approach does not directly provide an efficient method to find the policies. An iterative algorithm for policies with the simple form is proposed and investigated. The algorithm alternates between paging policy optimization and registration policy optimization. It finds a pair of individually optimal policies, but an example is given showing that the policies need not be jointly optimal.

Jointly optimal paging and registration policies are identified for a cellular network composed of a linear array of cells. Motion is modeled as a random walk with a symmetric, unimodal step size distribution. Minimization of the discounted, infinite-horizon average cost is addressed. The jointly optimal pair of paging and registration policies is found. The optimal registration policy is a distance threshold type: the mobile station. registers whenever its distance from the previous reporting point exceeds a-threshold. The paging policy is ping-pong type: cells are searched in an order of increasing distance from the cell in which the previous report occurred.

This paper focuses on jammed timing channels. Pure delay jammers with a maximum delay constraint, an average delay constraint, or a maximum buffer size constraint are explored, for continuous-time or discrete-time packet waveforms. Fluid waveform approximations of each of these classes of waveforms are employed to aid in analysis. Channel capacity is defined and an information-theoretic game based on mutual information rate is studied. Min-max optimal jammers and max-min optimal input processes are sought. Bounds on the min-max and max-min mutual information rates are described, and numerical examples are given. For maximum-delay-constrained (MDC) jammers with continuous-time packet waveforms, saddle-point input and jammer strategies are identified. The capacity of the maximum-delay constrained jamming channel with continuous-time packet waveforms is shown to equal the mutual information rate of the saddle point. For MDC jammers with discrete-time packet waveforms, saddle-point strategies are shown to exist. Jammers which have quantized batch departures at regular intervals are shown to perform well. Input processes with batches at regular intervals perform well for MDC or maximum-buffer-size-constrained jammers.

The capacity and the reliability function as the peak constraint tends to zero are considered for a discrete-time memoryless channel with peak constrained inputs. Prelov and van der Meulen (1993) showed that under mild conditions the ratio of the capacity to the squared peak constraint converges to one-half the maximum eigenvalue of the Fisher information matrix and if the Fisher information matrix is nonzero, the asymptotically optimal input distribution is symmetric antipodal signaling. Under similar conditions, it is shown in the first part of the paper that the reliability function has the same asymptotic shape as the reliability function for the power-constrained infinite bandwidth white Gaussian noise channel. The second part of the paper deals with Rayleigh-fading channels. For such channels, the Fisher information matrix is zero, indicating the difficulty of transmission over such channels with small peak constrained signals. Asymptotics for the Rayleigh channel are derived and applied to obtain the asymptotics of the capacity of the Marzetta and Hochwald (1999) fading channel model for small peak constraints, and to obtain a result of the type of Medard and Gallager for wide-band fading channels.

Medard and Gallager (2002) showed that very large bandwidths on certain fading channels cannot be effectively used by direct sequence or related spread-spectrum systems. This paper complements the work of Medard and Gallager. First, it is shown that a key information-theoretic inequality of Medard and Gallager can be directly derived using the theory of capacity per unit cost, for a certain fourth-order cost function, called fourthegy. This provides insight into the tightness of the bound. Secondly, the bound is explored for a wide-sense-stationary uncorrelated scattering (WSSUS) fading channel, which entails mathematically defining such a channel. In this context, the fourthegy can be expressed using the ambiguity function of the input signal. Finally, numerical data and conclusions are presented for direct-sequence type input signals.

Information theory has not yet had a direct impact on networking, although there are similarities in concepts and methodologies that have consistently attracted the attention of researchers from both fields. In this paper, we review several topics that are related to communication networks and that have an information-theoretic flavor, including multiaccess protocols, timing channels, effective bandwidth of bursty data sources, deterministic constraints on datastreams, queuing theory, and switching networks.

This paper explores the variations in mean queue length for stationary arrival processes with the same mean and autocorrelation functions, or equivalently, the same mean and power spectrum. Three types of processes, namely, two-state Markov-modulated Poisson processes, periodic-sequence modulated Poisson processes and processes generated by randomly filtering a white noise process, are investigated. Results show that the mean queue length can vary substantially for the first type of process, and can vary moderately for the second type of process, as the parameters of the processes are varied, subject to a specified mean and autocorrelation function. However, the mean queue lengths for the third type of arrival processes are determined by the input mean and autocorrelation functions. The results suggest that the queueing performance can be hard to predict from spectral data alone when the power in low frequencies is large.

The probability of capture under a model (for a land mobile radio direct sequence spread spectrum system) based on the ratio of the largest received power to the sum of interference powers is examined in the limit of a large number of transmitting stations. It is shown in great generality that the limit depends only on the capture ratio threshold and the roll-off exponent of the distribution of power received from a typical station. This exponent is insensitive to many typical channel effects such as Rician or Rayleigh fading and log-normal shadowing. The model is suitable for large systems with noncoherently combined interference.

A new model of nonuniform traffic is introduced for a single-hop packet-switching system. This traffic model allows arbitrary traffic streams subject only to a constraint on the number of data packets which can arrive at any, individual source in the system or for any individual destination in the system over time periods of specified length. The nonuniform traffic model is flexible enough to cover integrated data networks carrying diverse classes of data. The system model is rather general, and includes passive optical star wavelength-division networks. Transmission algorithms are introduced for a single-hop packet-switching system with such nonuniform traffic and with propagation delay that is negligible relative to the packet length. The algorithms are based on collision-free scheduling of packets using graph-matching algorithms since the global state of the system is known to all stations at any time.

The paper focuses on the dynamic resource allocation problem. In communication networks such as wireless or circuit switching networks, resources correspond to base stations or links, and the load corresponds to the calls in the network. The principle of load balancing is examined for dynamic resource allocation. The question of interest is the performance of simple allocation strategies which can be implemented online. Either finite capacity constraints on resources or mobility of users can be incorporated into the setup. The load balancing problem is formulated as an optimal control problem, and variants of a simple "least loaded routing" policy are shown to be asymptotically optimal for large call arrival rates.

Transmission algorithms are introduced for use in a single-hop packet switching system with nonuniform traffic and with propagation delay that Is large relative to the packet transmission time. The traffic model allows arbitrary traffic streams subject only to a constraint on the number of data packets which can arrive at any individual source in the system or for any individual destination in the system over time periods of specified length. The algorithms are based primarily on sending transmission schedules to the receivers immediately before transmitting each data packet multiple times so that the receiver can maximize the number of packets it captures. An algorithm based on matchings in a random graph is shown to provide mean total delay divided by mean propagation delay arbitrarily close to one, as the propagation delay tends to infinity.>

A new model of nonuniform traffic is introduced for a single-hop packet switching system. This traffic model allows arbitrary traffic streams subject only to a constraint on the number of data packets which can arrive at any individual source in the system or for any individual destination in the system over time periods of specified length. The nonuniform traffic model is flexible enough to cover integrated data networks carrying diverse classes of data. The system model is rather general and includes passive optical star wavelength division networks. Transmission algorithms are introduced for a single-hop packet switching system with such nonuniform traffic and with propagation delay that is negligible relative to the packet length. The algorithms are based on collision-free scheduling of packets using graph matching algorithms, since the global state of the system is known to all stations at any time.>

Abstract We present an algorithm that does packet routing on an N‐node butterfly in time O(log N) with small constants. The algorithm is based on Ranade's probabilistic PRAM emulation. We simplify the algorithm by focusing on packet routing and prove bounds on its performance for the cases of permutation routing and uniform, random traffic. The main results are upper bounds on the probability that the routing time exceeds t for a fixed queue size. The simplifications made to Ranade's original algorithm and a more careful analysis enabled us to achieve better constants, which, to the best of our knowledge, are the best to date. © 1994 by John Wiley & Sons, Inc.

S. Badr and P. Podar (1989) introduced a zig-zag routing policy and showed its optimality for shortest-path routing on square or infinite grid networks with independent link failures. This paper shows that, contrary to the claim of Badr and Podar, a zig-zag policy is not optimal for shortest-path routing on torus networks.>

The effect that large propagation delay has on the problem of network access is explored for the infinite population model with success-idle-collision feedback information, where the feedback information suffers a large propagation delay N. A simple lower bound is given on the probability that a packet is not successfully transmitted within N/2 time units (not including the forward propagation delay), where N is the station-to-station propagation delay. The bound implies a lower bound on the mean access delay. We also display an algorithm for which the transmission delay is within a factor of three of the lower bound, for moderate traffic loads and asymptotically large propagation delay.>

Simple expressions are given for the mean delay, mean waiting time, and mean busy period length in a multiplexer. A large class of possible data streams is considered. For example, data streams with active periods having a general distribution are permitted, and the traffic rate during the active periods can be random. Data can also arrive in batches. The output stream of the multiplexer again falls into the class. The exact formulas allow evaluation of the error in approximations such as a heavy traffic diffusion approximation. Both continuous-time and discrete-time models are treated. The Pollaczek-Khinchine formula for the mean amount of work in an M/G/1 queue is retrieved as a limiting case.>

Consider a packet walking along a directed graph with each node having two edges directed out. The packet is headed towards one of N destinations, chosen according to a probability distribution p. At each step, the packet is forced to use a nonpreferred edge with some probability q, independently of past events. Using information theory and sequential analysis, it is shown that the mean number of steps required by the packet to reach the destination is roughly, at least H(p)/(1-h(q), where h is the binary entropy function and H(p) is the entropy (base two) of p. This lower bound is shown to be asymptotically achievable in the case where the packet always begins at a fixed node. Also considered is the maximum, over all pairs of nodes in a graph, of the mean transit time from one node to the other. The work is motivated by the search for graphs that work well in conjunction with deflection routing in communication networks.>

An approximate analysis of the transient and steady state behavior of deflection routing in hypercube networks is presented, under a uniform traffic model. In deflection routing congestion causes packets admitted to the network to be temporarily misrouted rather than buffered or dropped. The approximations show that deflection routing performs remarkably well in hypercube networks, for small as well as large networks and for the whole range from light to heavy load. Simulations suggest that the approximations are quite accurate.>

Decoding algorithms in which unpruned codeword trees are generated from an ordered list of parity checks are investigated. The order is computed from the received message, and low-density parity-check codes are used to help control the growth of the tree. Simulation results are given for the binary erasure channel. They suggest that for the small erasure probability, the method is computationally feasible at rates above the computational cutoff rate.>

An algorithm is presented that does packet routing on an N-node butterfly in time O(log N) with small constants. The algorithm is based on A. Ranade's (1987) probabilistic random access machine (PRAM) emulation. The algorithm is simplified by focusing on packet routing. Bounds on the performance of the algorithm are proven for permutation routing and uniform random traffic. The main results are upper bounds on the probability that the routing time exceeds t for a fixed queue size. The constants achieved are the best to date. A complete description of the routing algorithm is given.>

It is shown that if formulas constructed from error-prone three-input gates are used to compute Boolean functions, then a per-gate failure probability of 1/6 or more cannot be tolerated. The result is shown to be tight if the per-gate failure probability is constant and precisely known.>

Four packet-switched networks using shuffle-exchange interconnections and deflection routing are analyzed. The first two are well-known networks based solely on shuffle interconnections, and the other two are variations in which the negative effects of deflection are reduced. Approximate state equations are given under a uniform traffic assumption. The equations predict the distribution of packet delay and can be used in situations where packets are assigned priorities. The four networks are briefly compared to each other and to Batcher-Banyan sorting networks and hypercube deflection networks.>

A set of M resource locations and a set of alpha M consumers are given. Each consumer requires a specified amount of resource, and is constrained to obtain the resource from a specified subset of locations. The problem of assigning consumers to resource locations so as to balance the load among the resource locations as much as possible is considered. It is shown that there are assignments, termed uniformly most-balanced assignments, that simultaneously minimize certain symmetric, separable, convex cost functions. The problem of finding such assignments is equivalent to a network flow problem with convex cost. Algorithms of both the iterative and combinatorial type are given for computing the assignments. The distribution function of the load at a given location for a uniformly most-balanced assignment is studied, assuming that the set of locations each consumer can use is random. An asymptotic lower bound on the distribution function is given for M tending to infinity, and an upper bound is given on the probable maximum load. It is shown that there is typically a large set of resource locations that all have the minimum load, and that for large average loads the maximum load is near the average load.>

The random, heuristic search algorithm called simulated annealing is considered for the problem of finding the maximum cardinality matching in a graph. It is shown that neither a basic form of the algorithm, nor any other algorithm in a fairly large related class of algorithms, can find maximum cardinality matchings such that the average time required grows as a polynomial in the number of nodes of the graph. In contrast, it is also shown for arbitrary graphs that a degenerate form of the basic annealing algorithm (obtained by letting “temperature” be a suitably chosen constant) produces matchings with nearly maximum cardinality in polynomial average time.

Two polynomial-time algorithms are given for scheduling conversations in a spread spectrum radio network. The constraint on conversations is that each station can converse with only one other station at a time. The first algorithm is strongly polynomial and finds a schedule of minimum length that allows each pair of neighboring stations to converse directly for a prescribed length of time. The second algorithm is designed for the situation in which messages must be relayed multiple hops. The algorithm produces, in polynomial time, a routing vector and compatible link schedule that jointly meet a prespecified end-to-end demand, so that the schedule has the smallest possible length.>

In this paper, we present iterative methods for finding optimal state-dependent routing strategies in single commodity networks. The key to our method is to show that there exists a family of optimization problems with convex cost and linear constraints that have solutions that can be converted into an optimal routing strategy by way of a flow relaxation transformation. These problems, when solved by certain iterative algorithms, lead to different convergence rates. In particular, one of the problems has quadratic cost. To solve one of these optimization problems, we use an iterative projected descent direction algorithm due to Bertsekas. We present an alternative to the Armijo-like step size rule of the algorithm, which we believe is more robust. Also included are Newton-like descent directions that take a reasonable amount of time to compute. Finally, some results of our computer experiments are summarized.

Consider a stationary Gaussian process withEX_{i}X_{j}=a^{|i-j|}where0 < a < 1,nd let0 < r < 1. It is shown that to locate the maximum ofX_{l}, X_{2}, \cdots, X_{N}for largeNwith probabilityr, roughly-rN \log a/\log\log Nobservations at sequentially determined locations are both sufficient and necessary.

Strategies based on stochastic approximation are suggested for controlling the transmission probabilities of stations sharing a collision access communication channel. Examples include strategies based on acknowledgment feedback only, and strategies suitable for frequency-hopped spread spectrum channels. The strategies provide for the incorporation of priorities among the stations. A Lyapunov-like function is constructed to prove global stability of the ordinary differential equation which is approximated by the system, and a design methodology based on minimizing a cost function is given. Preliminary results on transmission control in a nonbroadcast network are presented.

Abstract New characterizations of optimal state‐dependent routing strategies are obtained for the continuous traffic network model proposed by Segall for linear cost with unity weighting at each node and for constant inputs. The concept of flow relaxation is introduced and is used t o transform the optimal routing problem into an initial flow optimization problem with convex cost and linear constraints. Three algorithms are given for open‐loop computation of the optimal initial flow. The first is a simple iterative algorithm based on gradient descent with bending and it is well suited for decentralized computation. The second algorithm reduces the problem t o a series of max‐flow problems and it computes the exact optimal initial flow in O(lN14) compu‐ tations, where IN1 is the number of nodes in the network. The third algorithm is based on a search for successive bottlenecks in the network.

It is shown that among all arrival processes (not necessarily stationary or renewal type) for an exponential server queue with specified arrival and service rates, that the arrival process which mmimizes the average delay and related quantities is the process with constant interarrival times.The proof is based on a convexity property of exponential server queues which is of independent interest.The folk theorem provides a lower bound, which is readily computable by existing methods, to the average delay in a network of queues under rather general routing disciplines.A sharper lower bound on average delay is provided for the special case of Generalized Round Robin routing for a Poisson arrival process.

A new upper bound of0.6126packets/slot is established for the through-put of a time-slotted multi-access broadcast channel subject to an infinite population of user stations (whose transmissions are modeled by a Poisson process) using (0)-, (1)-, (e)-feedback to denote a slot with none, one, or at least two packets, respectively.

Two notions of information-singular and strong information-singular random processes were proposed by Berger as processes which are deterministic or negligible in a physically meaningful, information theoretic sense. This paper serves two purposes. First, it shows that strong information-singularity of a random process is equivalent to information-singularity plus a quite different property called recoverability. Secondly, it shows that these properties can be completely characterized in the case where the processes of interest are (jointly) stationary and satisfy a mild integrability condition.

The minimum amount of information and the asymptotic minimum amount of entropy of a random partition which separates the points of a Poisson point process are found. Related information theoretic bounds are applied to yield an upper bound to the throughput of a random access broadcast channel. It is shown that more information is needed to separate points by partitions consisting of intervals than by general partitions. This suggests that single-interval conflict resolution algorithms may not achieve maximum efficiency.

In an exploratory paper, T. Berger studied discrete random processes which generate information slower than linearly with time. One of his objectives was to provide a physically meaningful definition of a deterministic process, and to this end he introduced the notion of strong information singularity. His work is supplemented by demonstrating that a large class of convariance stationary processes are strongly information singular with respect to a class of stationary Gaussian processes. One important consequence is that for a large class of covariance stationary processes the information rate equals that of the process associated with the Brownian motion component of the spectral representation. In an exploratory paper, T. Berger studied discrete random processes which generate information slower than linearly with time. One of his objectives was to provide a physically meaningful definition of a deterministic process, and to this end he introduced the notion of strong information singularity. His work is supplemented by demonstrating that a large class of convariance stationary processes are strongly information singular with respect to a class of stationary Gaussian processes. One important consequence is that for a large class of covariance stationary processes the information rate equals that of the process associated with the Brownian motion component of the spectral representation. In an exploratory paper, T. Berger studied discrete random In an exploratory paper, T. Berger studied discrete random processes which generate information slower than linearly with time. One of his objectives was to provide a physically meaningful definition of a deterministic process, and to this end he introduced the notion of strong information singularity. His work is supplemented by demonstrating that a large class of convariance stationary processes are strongly information singular with respect to a class of stationary Gaussian processes. One important consequence is that for a large class of covariance stationary processes the information rate equals that of the process associated with the Brownian motion component of the spectral representation.

Tbe problem of transmission of separate messages to each of two receivers over a general binary-input broadcast channel is investigated. A new approach to a class of information-theoretic problems is developed and applied to obtain bounds on the cardinalities of auxiliary random variables. These bounds permit the calculation of two different regions of achievable rate pairs which are derived from the Cover-van der Meulen region{\cal R}of achievable rate triples. Numerical evaluation of these regions of rate pairs for two examples demonstrates that the region{\cal R}can be enlarged. This enlargement is accomplished by making{\cal R}internally consistent, as the true capacity region must be. The results display complex interactions between common and separate information in broadcast problems.