Arash Gholami Davoodi, Seyed Pouyan Mousavi Davoudi, Pouya Pezeshkpour. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2025.

Finding associations between pairs of variables in large datasets is crucial for various disciplines. The brute force method for solving this problem requires computing the mutual information between $\binom{N}{2}$ pairs. In this paper, we consider the problem of finding pairs of variables with high mutual information in sub-quadratic complexity. This problem is analogous to the nearest neighbor search, where the goal is to find pairs among $N$ variables that are similar to each other. To solve this problem, we develop a new algorithm for finding associations based on constructing a decision tree that assigns a hash to each variable, in a way that for pairs with higher mutual information, the chance of having the same hash is higher. For any $1 \leq \lambda \leq 2$, we prove that in the case of binary data, we can reduce the number of necessary mutual information computations for finding all pairs satisfying $I(X, Y) > 2- \lambda$ from $O(N^2)$ to $O(N^\lambda)$, where $I(X,Y)$ is the empirical mutual information between variables $X$ and $Y$. Finally, we confirmed our theory by experiments on simulated and real data. The implementation of our method and experiments is publicly available at \href{https://github.com/mohimanilab/HashMI}{https://github.com/mohimanilab/HashMI}.

In this work, we study the impact of imperfect sharing of the Channel State Information (CSI) available at the transmitters on a Network MIMO setting in which a set of M transmit antennas, possibly not co-located, jointly serve two multi-antenna users endowed with N1and N2antennas, respectively. We consider the case where only a subset of k transmit antennas have access to perfect CSI, whereas the other M - k transmit antennas have only access to finite precision CSI. The analysis of this configuration aims to answer the question of how much an extra informed antenna can help. We model this scenario as a Decentralized MIMO Broadcast Channel (BC) and characterize the Degrees-of-Freedom (DoF) region, showing that only k = max(N1, N2) antennas with perfect CSI are needed to achieve the DoF of the conventional BC with ubiquitous perfect CSI.

The degrees of freedom (DoF) region is characterized for the 2-user multiple input multiple output (MIMO) broadcast channel (BC), where the transmitter is equipped with M antennas, the two receivers are equipped with N1and N2antennas, and the levels of channel state information at the transmitter (CSIT) for the two users are parameterized by β1, β2, respectively. The achievability of the DoF region was established by Hao, Rassouli and Clerckx, but no proof of optimality was heretofore available. The proof of optimality is provided in this work with the aid of sum-set inequalities based on the aligned image sets (AIS) approach.

The degrees of freedom (DoF) region is characterized for the 2-user multiple input multiple output (MIMO) broadcast channel (BC), where the transmitter is equipped with M antennas, the two receivers are equipped with N1and N2antennas, and the levels of channel state information at the transmitter (CSIT) for the two users are parameterized by β1, β2, respectively. The achievability of the DoF region was established by Hao, Rassouli and Clerckx, but no proof of optimality was heretofore available. The proof of optimality is provided in this work with the aid of sum-set inequalities based on the aligned image sets (AIS) approach.

The recipients of the 2018 IEEE Communications Society and Information Theory Society Joint Paper Award are Arash Gholami Davoodi and Syed A. Jafar for the paper “Aligned Image Sets Under Channel Uncertainty: Settling Conjectures on the Collapse of Degrees of Freedom Under Finite Precision CSIT” which appeared in the IEEE Transactions on Information Theory, vol. 62, no. 10, pp. 5603–5618, October 2016.

The generalized degrees of freedom of the two-user symmetric multiple input multiple output interference channel are characterized as a function of the channel strength levels and the level of channel state information at the transmitters. In this symmetric setting, each transmitter is equipped with M antennas, each receiver is equipped with N antennas, and both cross links have the same strength parameter α and the same channel uncertainty parameter β. The main challenge resides in the proof of the outer bound which is accomplished by a generalization of the aligned image sets approach.

Generalized degrees of freedom (GDoF) are characterized for the symmetric K-user multiple-input multiple-output interference channel under the assumption that the channel-state information at the transmitters (CSITs) is limited to finite precision. In this symmetric setting, each transmitter is equipped with M antennas, each receiver is equipped with N antennas, each desired channel (i.e., a channel between a transmit antenna and a receive antenna belonging to the same user) has strength ~P, while each undesired channel has strength ~Pα, where P is a nominal SNR parameter. The result generalizes a previous GDoF characterization for the SISO setting (M = N = 1) and is enabled by a significant extension of the aligned image sets bound that is broadly useful. GDoF per user take the form of a W-curve with respect to α for fixed values of M and N. Under finite precision CSIT, in spite of the presence of multiple antennas, all the benefits of interference alignment are lost.

We study the K = 3 user multiple input single output (MISO) broadcast channel (BC) with M = 3 antennas at the transmitter and 1 antenna at each receiver, from the generalized degrees of freedom (GDoF) perspective, under the assumption that the channel state information at the transmitter (CSIT) is limited to the finite precision. In particular, our goal is to identify a parameter regime where a simple layered superposition (SLS) coding scheme achieves the entire GDoF region. With αijrepresenting the channel strength parameter for the link from the jthantenna of the transmitter to the jthreceiver, we prove that the SLS is GDoF optimal without the need for time-sharing if max(αki, αim) ≤ αiiand αki+ αim≤ αii+ αkmfor all i, k ∈ [3], m ∈ [M]. The GDoF region under this condition is a convex polyhedron. The result generalizes to arbitrary M ≥ 3.

We study K-user Interference Channels (IC), K-user MIMO ICs and K-user MIMO Broadcast Channels (BC) with generic channel coefficients where, for some channel coefficients the channel state information at the transmitter(s) (CSIT) is perfect, while for the others the CSIT is available only to finite precision. By generalizing the Aligned Image Sets (AIS) bound we are able to characterize the necessary and sufficient condition for the collapse of sum degrees of freedom (DoF) to 1 in each case. For example, the K=3 user interference channel has sum DoF=1 if and only if the CSIT for at least one of the undesired channel coefficients is limited to finite precision.

This paper obtains the first degrees of freedom (DoFs) bound that is provably sensitive to network coherence time, i.e., coherence time in an interference network, where all channels experience the same coherence patterns. This is accomplished by a novel adaptation of the aligned image sets bound and settles various open problems noted previously by Naderi and Avestimehr and by Gou et al. For example, a necessary and sufficient condition is obtained for the optimality of 1/2 DoF per user in a partially connected interference network, where the channel state information at the receivers (CSIRs) is perfect, the channel state information at the transmitters (CSITs) is instantaneous but limited to finite precision, and the network coherence time is Tc=1. The surprising insight that emerges is that even with perfect CSIR and instantaneous finite precision CSIT, the network coherence time matters, i.e., it has a DoF impact.

For the $K=2$ user MISO BC, i.e., the wireless broadcast channel where a transmitter equipped with $K=2$ antennas sends independent messages to $K=2$ receivers each of which is equipped with a single antenna, the generalized degrees of freedom (GDoFs) region are characterized for arbitrary channel strength and channel uncertainty levels for each of the channel coefficients. The result is extended to K>2 users under additional restrictions which include the assumption of symmetry.

The generalized degrees of freedom (GDoF) of the two user symmetric multiple input multiple output (MIMO) interference channel (IC) are characterized as a function of the channel strength levels and the level of channel state information at the transmitters (CSIT). In this symmetric setting, each transmitter is equipped with M antennas, each receiver is equipped with N antennas, and both cross links have the same strength parameter α and the same channel uncertainty parameter β. The main challenge resides in the proof of the outer bound which is accomplished by a generalization of the aligned image sets approach.

This work obtains the first degrees of freedom (DoF) bound that is sensitive to network coherence time, i.e., coherence time in an interference network where all channels experience the same coherence patterns. This is accomplished by a novel adaptation of the aligned image sets bound, and settles various open problems noted previously by Naderi and Avestimehr and by Gou et al. For example, a necessary and sufficient condition is obtained for the optimality of 1/2 DoF per user in a partially connected interference network where the channel state information at the receivers (CSIR) is perfect, the channel state information at the transmitters (CSIT) is instantaneous but limited to finite precision, and the network coherence time is Tc = 1. The broader insight that emerges is that even with perfect CSIR and instantaneous finite precision CSIT, network coherence time matters, i.e., it has a DoF impact.

We present sum-set inequalities specialized to the generalized degrees of freedom (GDoF) framework. These are information theoretic lower bounds on the entropy of bounded density linear combinations of discrete, power-limited dependent random variables in terms of the joint entropies of arbitrary linear combinations of new random variables that are obtained by power level partitioning of the original random variables. These bounds generalize the aligned image sets approach, and are useful instruments to obtain GDoF characterizations for wireless networks, especially with multiple antenna nodes, subject to arbitrary channel strength and channel uncertainty levels. To demonstrate the utility of these bounds, we consider various examples of interference and broadcast channels for which we obtain tight GDoF characterizations with the aid of sum-set inequalities.

The benefits of partial and full transmitter cooperation are evaluated for a two user interference channel under finite precision channel state information at the transmitters (CSITs), using the generalized degrees of freedom (GDoFs) metric. Under finite precision CSIT, the benefits of interference alignment are completely lost, so that the X channel obtained by partial transmitter cooperation does no better than the underlying interference channels. Full transmitter cooperation produces a vector broadcast channel, which has a strict GDoF advantage over partial cooperation (X channel) and whose GDoF is fully achieved by interference enhancement.

The generalized degrees of freedom (GDoF) characterization of the symmetric K user interference channel is obtained under finite precision channel state information at the transmitters (CSIT). The symmetric setting is where each cross channel is capable of carrying α DoF, while each direct channel is capable of carrying 1 DoF. Remarkably, under finite precision CSIT the symmetric K user interference channel loses all the GDoF benefits of interference alignment. The GDoF per user diminish with the number of users everywhere except in the very strong (optimal for every receiver to decode all messages) and very weak (optimal to treat all interference as noise) interference regimes. The result stands in sharp contrast to prior work on the symmetric setting under perfect CSIT, where the GDoF per user remain undiminished due to interference alignment. The result also stands in contrast to prior work on a subclass of asymmetric settings under finite precision CSIT, i.e., the topological interference management problem, where interference alignment plays a crucial role and provides substantial GDoF benefits.

This work bridges the gap between sharply contrasting results on the degrees of freedom of the K user broadcast channel where the transmitter is equipped with K transmit antennas and each of the K receivers is equipped with a single antenna. This channel has K DoF when channel state information at the transmitter (CSIT) is perfect, but as shown recently, it has only 1 DoF when the CSIT is limited to finite precision. By considering the full range of partial CSIT assumptions parameterized by β ∈ [0,1], such that the strength of the channel estimation error terms scales as ~ SNR-βrelative to the channel strengths which scale as ~ SNR, it is shown that this channel has 1 - β + Kβ DoF. For K = 2 users with arbitrary βijparameters, the DoF are shown to be 1 + mini,jβij. To explore diversity of channel strengths, the results are further extended to the symmetric Generalized Degrees of Freedom setting where the direct channel strengths scale as ~ SNR and the cross channel strengths scale as ~ SNRα, α ∈ [0,1], β ∈ [0,α]. Here, the roles of α and β are shown to counter each other on equal terms, so that the sum GDoF value in the K user setting is (α - β) + K(1 - (α-β )) and for the 2 user setting with arbitrary βij, is 2 - α + mini,jβij.

The generalized degrees of freedom (GDoF) characterization of the symmetric K-user interference channel is obtained under finite precision channel state information at the transmitters (CSIT). The symmetric setting is where each cross channel is capable of carrying α degrees of freedom (DoF) while each direct channel is capable of carrying 1 DoF. Remarkably, under finite precision CSIT the symmetric K-user interference channel loses all the GDoF benefits of interference alignment. The GDoF per user diminish with the number of users everywhere except in the very strong (optimal for every receiver to decode all messages) and very weak (optimal to treat all interference as noise) interference regimes. The result stands in sharp contrast to prior work on the symmetric setting under perfect CSIT, where the GDoF per user remain undiminished due to interference alignment. The result also stands in contrast to prior work on a subclass of asymmetric settings under finite precision CSIT, i.e., the topological interference management problem, where interference alignment plays a crucial role and provides substantial GDoF benefits.

A conjecture made by Lapidoth et al. at Allerton 2005 (also an open problem presented at ITA 2006) states that the degrees of freedom (DoF) of a two user broadcast channel, where the transmitter is equipped with two antennas and each user is equipped with one antenna, must collapse under finite precision channel state information at the transmitter (CSIT). That this conjecture, which predates interference alignment, has remained unresolved, is emblematic of a pervasive lack of understanding of the DoF of wireless networks-including interference and X networks-under channel uncertainty at the transmitter(s). In this paper, we prove that the conjecture is true in all non-degenerate settings (e.g., where the probability density function of unknown channel coefficients exists and is bounded). The DoF collapse even when perfect channel knowledge for one user is available to the transmitter. This also settles a related recent conjecture by Tandon et al. The key to our proof is a bound on the number of codewords that can cast the same image (within noise distortion) at the undesired receiver whose channel is subject to finite precision CSIT, while remaining resolvable at the desired receiver whose channel is precisely known by the transmitter. We are also able to generalize the result along two directions. First, if the peak of the probability density function is √ allowed to scale as O(( √P)α), representing the concentration of probability density (improving CSIT) due to, e.g., quantized feedback at rate (α/2) log(P), then the DoF is bounded above by 1+α, which is also achievable under quantized feedback. Second, we generalize the result to arbitrary number of antennas at the transmitter, arbitrary number of single-antenna users, and complex channels. The generalization directly implies a collapse of DoF to unity under non-degenerate channel uncertainty for the general K-user interference and M × N user X networks as well.

The benefits of partial and full transmitter cooperation are evaluated for a two user interference channel under finite precision channel state information at the transmitters (CSIT), using the generalized degrees of freedom (GDoF) metric. Under finite precision CSIT, the benefits of interference alignment are completely lost, so that the X channel obtained by partial transmitter cooperation does no better than the underlying interference channels. Full transmitter cooperation produces a vector broadcast channel (BC) which has a strict GDoF advantage over partial cooperation (X channel) and whose GDoF are fully achieved by interference enhancement.

A conjecture made by Lapidoth, Shamai and Wigger at Allerton 2005 (also an open problem presented at ITA 2006) states that the degrees of freedom (DoF) of a two user broadcast channel, where the transmitter is equipped with 2 antennas and each user is equipped with 1 antenna, must collapse under finite precision channel state information at the transmitter (CSIT). That this conjecture, which predates interference alignment, has remained unresolved, is emblematic of a pervasive lack of understanding of the degrees of freedom of wireless networks-including interference and X networks-under channel uncertainty at the transmitter(s). In this work we prove that the conjecture is true in all non-degenerate settings (e.g., where the probability density function of unknown channel coefficients exists and is bounded). The DoF collapse even when perfect channel knowledge for one user is available to the transmitter. This also settles a related recent conjecture by Tandon et al. Reminiscent of Korner and Marton's work on the images of a set, the key to our proof is a bound on the number of codewords that can cast the same image (within noise distortion) at the undesired receiver, while remaining resolvable at the desired receiver. We are also able to generalize the result to arbitrary number of users, including the K user interference channel. Remarkably, for the K user interference channel, this work and the earlier work by Cadambe and Jafar reveal two contrasting sides of the same coin. Both works close a gap between the best previously known DoF inner bound of 1 and the best previously known DoF outer bound of K/2. However, while Cadambe and Jafar do so in the optimistic direction, showing that K/2 is optimal under perfect CSIT, here we close the gap in the pessimistic direction, showing that 1 DoF is optimal under finite precision CSIT.

For a fading full‐duplex decode‐and‐forward relay channel, the authors analytically derive optimum power allocation schemes subject to individual power constraints at the source and the relay. The authors prove that the problem is a convex optimisation problem over the feasible power set, and by proposing a systematic technique to solve min–max problems, optimum power allocations are derived in closed‐forms. Finally, for a Rayleigh‐fading channel model, optimum power allocations are derived and the respective achievable rate and an upper bound are evaluated. The implications of the derived theoretical results are discussed through some graphs.

In this paper, lattice based coding is used over two-user Gaussian state-dependent multiple access channel with common message for two channel models. First, it is assumed that the additive channel interference is noncausally known at both encoders. Exploiting a lattice encoding and decoding scheme, the effect of the interference is completely removed and the capacity region is achieved. Then, the multiple access channel with two additive interferences is considered in the case, where each interference is known noncausally to the associated transmitter. A pure lattice based encoding and decoding structure is proposed and an inner bound on the capacity region is derived which is valid for the entire range of channel signal to noise ratio and powers of interferences.