Nadim Ghaddar
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Nadim Ghaddar has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Lele Wang
Department of Electrical and Computer Engineering, The University of British Columbia, Vancouver, BC, Canada
5 shared publications - Ziao Wang
Department of Electrical and Computer Engineering, The University of British Columbia, Vancouver, BC, Canada
3 shared publications - Banghua Zhu
Department of Electrical Engineering and Computer Sciences UC Berkeley
2 shared publications - Young-Han Kim
Department of Electrical and Computer Engineering, University of California at San Diego, La Jolla, CA, USA
2 shared publications Banghua Zhu
Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA, USA
1 shared publicationByung K. Yi
InterDigital Communications, LLC, Wilmington, DE, USA
1 shared publication
Latest Publications
- 1 October 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (10) , 7686-7708
Noisy Computing of the Threshold Function
- 1 October 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (10) , 7686-7708
Noisy Computing of the Threshold Function
- 28 August 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 5, 572-584
Low-Complexity Coding Techniques for Cloud Radio Access Networks
The problem of coding for the uplink and downlink of cloud radio access networks (C-RAN’s) with K users and L relays is considered. It is shown that low-complexity coding schemes that achieve any point in the rate-fronthaul region of joint coding and compression can be constructed starting from at most 4(K+L)-2 point-to-point codes designed for symmetric channels. This reduces the seemingly hard task of constructing good codes for C-RAN’s to the much better understood task of finding good codes for single-user channels. To show this result, an equivalence between the achievable rate-fronthaul regions of joint coding and successive coding is established. Then, rate-splitting and quantization-splitting techniques are used to show that the task of achieving a rate-fronthaul point in the joint coding region can be simplified to that of achieving a corner point in a higher-dimensional C-RAN problem. As a by-product, some interesting properties of the rate-fronthaul region of joint decoding for uplink C-RAN’s are also derived.
- 28 August 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 5, 572-584
Low-Complexity Coding Techniques for Cloud Radio Access Networks
The problem of coding for the uplink and downlink of cloud radio access networks (C-RAN’s) with K users and L relays is considered. It is shown that low-complexity coding schemes that achieve any point in the rate-fronthaul region of joint coding and compression can be constructed starting from at most 4(K+L)-2 point-to-point codes designed for symmetric channels. This reduces the seemingly hard task of constructing good codes for C-RAN’s to the much better understood task of finding good codes for single-user channels. To show this result, an equivalence between the achievable rate-fronthaul regions of joint coding and successive coding is established. Then, rate-splitting and quantization-splitting techniques are used to show that the task of achieving a rate-fronthaul point in the joint coding region can be simplified to that of achieving a corner point in a higher-dimensional C-RAN problem. As a by-product, some interesting properties of the rate-fronthaul region of joint decoding for uplink C-RAN’s are also derived.
- 8 July 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (9) , 6121-6138
Noisy Sorting Capacity
Sorting is the task of ordering n elements using pairwise comparisons. It is well known that $m=\Theta (n\log n)$ comparisons are both necessary and sufficient when the outcomes of the comparisons are observed with no noise. In this paper, we study the sorting problem when each comparison is incorrect with some fixed yet unknown probability p. Unlike the common approach in the literature which aims to minimize the number of pairwise comparisons m to achieve a given desired error probability, we consider randomized algorithms with expected number of queries $\textsf {E}[M]$ and aim at characterizing the maximal sorting rate $\frac {n\log n}{\mathop {\mathrm {\textsf {E}}}\nolimits [M]}$ such that the ordering of the elements can be estimated with a vanishing error probability asymptotically. The maximal rate is referred to as the noisy sorting capacity. In this work, we derive upper and lower bounds on the noisy sorting capacity. The two lower bounds — one for fixed-length algorithms and one for variable-length algorithms — are established by combining the insertion sort algorithm with the well-known Burnashev-Zigangirov algorithm for channel coding with feedback. Compared with existing methods, the proposed algorithms are universal in the sense that they do not require the knowledge of p, while maintaining a strictly positive sorting rate. Moreover, we derive a general upper bound on the noisy sorting capacity, along with an upper bound on the maximal rate that can be achieved by sorting algorithms that are based on insertion sort.
- 8 July 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (9) , 6121-6138
Noisy Sorting Capacity
Sorting is the task of ordering n elements using pairwise comparisons. It is well known that $m=\Theta (n\log n)$ comparisons are both necessary and sufficient when the outcomes of the comparisons are observed with no noise. In this paper, we study the sorting problem when each comparison is incorrect with some fixed yet unknown probability p. Unlike the common approach in the literature which aims to minimize the number of pairwise comparisons m to achieve a given desired error probability, we consider randomized algorithms with expected number of queries $\textsf {E}[M]$ and aim at characterizing the maximal sorting rate $\frac {n\log n}{\mathop {\mathrm {\textsf {E}}}\nolimits [M]}$ such that the ordering of the elements can be estimated with a vanishing error probability asymptotically. The maximal rate is referred to as the noisy sorting capacity. In this work, we derive upper and lower bounds on the noisy sorting capacity. The two lower bounds — one for fixed-length algorithms and one for variable-length algorithms — are established by combining the insertion sort algorithm with the well-known Burnashev-Zigangirov algorithm for channel coding with feedback. Compared with existing methods, the proposed algorithms are universal in the sense that they do not require the knowledge of p, while maintaining a strictly positive sorting rate. Moreover, we derive a general upper bound on the noisy sorting capacity, along with an upper bound on the maximal rate that can be achieved by sorting algorithms that are based on insertion sort.
- 6 May 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 5, 302-313
Noisy Computing of the OR and MAX Functions
We consider the problem of computing a function of n variables using noisy queries, where each query is incorrect with some fixed and known probability $p \in (0,1/2)$ . Specifically, we consider the computation of the $\textsf {OR}$ function of n bits (where queries correspond to noisy readings of the bits) and the $\textsf {MAX}$ function of n real numbers (where queries correspond to noisy pairwise comparisons). We show that an expected number of queries of $(1 \pm o(1)) {}\frac {n\log {}\frac {1}{\delta }}{D_{\textsf {KL}}(p \| 1-p)}$ is both sufficient and necessary to compute both functions with a vanishing error probability $\delta = o(1)$ , where $D_{\textsf {KL}}(p \| 1-p)$ denotes the Kullback-Leibler divergence between $\textsf {Bern}(p)$ and $\textsf {Bern}(1-p)$ distributions. Compared to previous work, our results tighten the dependence on p in both the upper and lower bounds for the two functions.
- 6 May 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 5, 302-313
Noisy Computing of the OR and MAX Functions
We consider the problem of computing a function of n variables using noisy queries, where each query is incorrect with some fixed and known probability $p \in (0,1/2)$ . Specifically, we consider the computation of the $\textsf {OR}$ function of n bits (where queries correspond to noisy readings of the bits) and the $\textsf {MAX}$ function of n real numbers (where queries correspond to noisy pairwise comparisons). We show that an expected number of queries of $(1 \pm o(1)) {}\frac {n\log {}\frac {1}{\delta }}{D_{\textsf {KL}}(p \| 1-p)}$ is both sufficient and necessary to compute both functions with a vanishing error probability $\delta = o(1)$ , where $D_{\textsf {KL}}(p \| 1-p)$ denotes the Kullback-Leibler divergence between $\textsf {Bern}(p)$ and $\textsf {Bern}(1-p)$ distributions. Compared to previous work, our results tighten the dependence on p in both the upper and lower bounds for the two functions.
- 13 October 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (2) , 865-903
A Lego-Brick Approach to Coding for Network Communication
Coding schemes for several problems in network information theory are constructed starting from point-to-point channel codes that are designed for symmetric channels. Given that the point-to-point codes satisfy certain properties pertaining to the rate, the error probability, and the distribution of decoded sequences, bounds on the performance of the coding schemes are derived and shown to hold irrespective of other properties of the codes. In particular, we consider the problems of lossless and lossy source coding, Slepian–Wolf coding, Wyner–Ziv coding, Berger–Tung coding, multiple description coding, asymmetric channel coding, Gelfand–Pinsker coding, coding for multiple access channels, Marton coding for broadcast channels, and coding for cloud radio access networks (C-RAN’s). We show that the coding schemes can achieve the best known inner bounds for these problems, provided that the constituent point-to-point channel codes are rate-optimal. This would allow one to leverage commercial off-the-shelf codes for point-to-point symmetric channels in the practical implementation of codes over networks. Simulation results demonstrate the gain of the proposed coding schemes compared to existing practical solutions to these problems.
- 13 October 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (2) , 865-903
A Lego-Brick Approach to Coding for Network Communication
Coding schemes for several problems in network information theory are constructed starting from point-to-point channel codes that are designed for symmetric channels. Given that the point-to-point codes satisfy certain properties pertaining to the rate, the error probability, and the distribution of decoded sequences, bounds on the performance of the coding schemes are derived and shown to hold irrespective of other properties of the codes. In particular, we consider the problems of lossless and lossy source coding, Slepian–Wolf coding, Wyner–Ziv coding, Berger–Tung coding, multiple description coding, asymmetric channel coding, Gelfand–Pinsker coding, coding for multiple access channels, Marton coding for broadcast channels, and coding for cloud radio access networks (C-RAN’s). We show that the coding schemes can achieve the best known inner bounds for these problems, provided that the constituent point-to-point channel codes are rate-optimal. This would allow one to leverage commercial off-the-shelf codes for point-to-point symmetric channels in the practical implementation of codes over networks. Simulation results demonstrate the gain of the proposed coding schemes compared to existing practical solutions to these problems.
- 21 July 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 69 (10) , 6575-6589
Joint Channel Estimation and Coding Over Channels With Memory Using Polar Codes
A joint channel estimation and channel coding scheme is presented for channels with memory using polar codes. Unlike the conventional approach of first estimating all channel parameters and then performing channel decoding separately, the proposed scheme incorporates a subset of reliable estimates of channel parameters into the decoding procedure and computes decoding metrics averaged over the statistical behavior of the channel. Specifically, decoding algorithms for finite-state Markov channels of any order, for the Gauss-Markov channel and for flat-fading channels are presented. Further, by adapting list decoding to identify reliably-decoded bits within a codeword, channel estimation and decoding steps are performed iteratively to boost the reliability of channel estimation as well as error correction. In order to improve the performance even further, a new pilot arrangement scheme is developed that utilizes the structure of polar codes and sends pilot symbols embedded within the polar codewords. This construction can be viewed as a new family of shortened polar codes that can be of independent interest. Simulation results demonstrate the benefit of the proposed approach compared to existing solutions.
- 21 July 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 69 (10) , 6575-6589
Joint Channel Estimation and Coding Over Channels With Memory Using Polar Codes
A joint channel estimation and channel coding scheme is presented for channels with memory using polar codes. Unlike the conventional approach of first estimating all channel parameters and then performing channel decoding separately, the proposed scheme incorporates a subset of reliable estimates of channel parameters into the decoding procedure and computes decoding metrics averaged over the statistical behavior of the channel. Specifically, decoding algorithms for finite-state Markov channels of any order, for the Gauss-Markov channel and for flat-fading channels are presented. Further, by adapting list decoding to identify reliably-decoded bits within a codeword, channel estimation and decoding steps are performed iteratively to boost the reliability of channel estimation as well as error correction. In order to improve the performance even further, a new pilot arrangement scheme is developed that utilizes the structure of polar codes and sends pilot symbols embedded within the polar codewords. This construction can be viewed as a new family of shortened polar codes that can be of independent interest. Simulation results demonstrate the benefit of the proposed approach compared to existing solutions.