Michael Langberg
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
Research Subjects
Michael Langberg has a total of 53 co-authors. Here are the top co-authors by number of shared publications:
- Michelle Effros
Department of Electrical Engineering, California Institute of Technology, Pasadena, CA, USA
22 shared publications - Parham Noorzad
California Institute of Technology, Pasadena, CA, USA
10 shared publications - Jorg Kliewer
Helen and John C. Hartmann Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ 07102, USA
6 shared publications - Bikash Kumar Dey
Department of Electrical Engineering, Indian Institute of Technology Bombay, Mumbai, India
4 shared publications - Mira Gonen
School of Computer Science, Ariel University, Ariel, Israel
4 shared publications Tracey Ho
Department of Electrical Engineering, California Institute of Technology, Pasadena, CA, USA
4 shared publications
Latest Publications
- 12 November 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Networking
- Vol. 34, 1538-1553
Dynamic D2D-Assisted Federated Learning Over O-RAN: Performance Analysis, MAC Scheduler, and Asymmetric User Selection
Existing studies on federated learning (FL) are mostly focused on system orchestration for static snapshots of the network and making static control decisions (e.g., spectrum allocation). However, real-world wireless networks are susceptible to temporal variations of wireless channel capacity and users’ datasets. In this paper, we study the impacts of the dynamics: 1) wireless channels and 2) users’ datasets on the FL execution. The former is captured by introducing a set of discrete time events while the latter is characterized by a novel ordinary differential equation and the metric of dynamic model drift, formulated via a partial differential inequality, drawing concrete analytical connections between the dynamics of users’ datasets and FL accuracy. We then propose dynamic cooperative FL with dedicated MAC schedulers (DCLM), exploiting the unique features of open radio access network (O-RAN) to execute FL. DCLM entails: 1) a hierarchical device-to-device (D2D)-assisted model training; 2) dynamic control decisions through dedicated O-RAN MAC schedulers; and 3) asymmetric user selection. We provide extensive theoretical analysis to study the convergence of DCLM and then aim to optimize its degrees of freedom (e.g., user selection and spectrum allocation) through a non-convex optimization problem. We develop a systematic and generic approach to obtain the solution for this problem. We finally show the efficiency of DCLM via numerical simulations and provide a series of future directions.
- 12 November 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Networking
- Vol. 34, 1538-1553
Dynamic D2D-Assisted Federated Learning Over O-RAN: Performance Analysis, MAC Scheduler, and Asymmetric User Selection
Existing studies on federated learning (FL) are mostly focused on system orchestration for static snapshots of the network and making static control decisions (e.g., spectrum allocation). However, real-world wireless networks are susceptible to temporal variations of wireless channel capacity and users’ datasets. In this paper, we study the impacts of the dynamics: 1) wireless channels and 2) users’ datasets on the FL execution. The former is captured by introducing a set of discrete time events while the latter is characterized by a novel ordinary differential equation and the metric of dynamic model drift, formulated via a partial differential inequality, drawing concrete analytical connections between the dynamics of users’ datasets and FL accuracy. We then propose dynamic cooperative FL with dedicated MAC schedulers (DCLM), exploiting the unique features of open radio access network (O-RAN) to execute FL. DCLM entails: 1) a hierarchical device-to-device (D2D)-assisted model training; 2) dynamic control decisions through dedicated O-RAN MAC schedulers; and 3) asymmetric user selection. We provide extensive theoretical analysis to study the convergence of DCLM and then aim to optimize its degrees of freedom (e.g., user selection and spectrum allocation) through a non-convex optimization problem. We develop a systematic and generic approach to obtain the solution for this problem. We finally show the efficiency of DCLM via numerical simulations and provide a series of future directions.
- Open Access
Sliding Window Adversarial Channels
In an arbitrarily varying channel (AVC), the channel has a state which is under the control of an adversarial jammer and the corresponding capacities are often functions of the "power" constraints on the transmitter and jammer. In this paper we propose a model in which the constraints must hold almost surely over contiguous subsequences of the codeword and state, which we call a sliding window constraint. We study oblivious jammers and codes with stochastic encoding under maximum probability of error. We show that this extra limitation on the jammer is beneficial for the transmitter: in some cases, the capacity for unique decoding with a sliding window constraint is equal to the capacity for list decoding in the standard model without sliding windows, roughly implying that the addition of window constraints reduces list decoding to unique decoding. The list decoding capacity in the standard model can be strictly larger than the unique decoding capacity.
Open AccessSliding Window Adversarial Channels
In an arbitrarily varying channel (AVC), the channel has a state which is under the control of an adversarial jammer and the corresponding capacities are often functions of the "power" constraints on the transmitter and jammer. In this paper we propose a model in which the constraints must hold almost surely over contiguous subsequences of the codeword and state, which we call a sliding window constraint. We study oblivious jammers and codes with stochastic encoding under maximum probability of error. We show that this extra limitation on the jammer is beneficial for the transmitter: in some cases, the capacity for unique decoding with a sliding window constraint is equal to the capacity for list decoding in the standard model without sliding windows, roughly implying that the addition of window constraints reduces list decoding to unique decoding. The list decoding capacity in the standard model can be strictly larger than the unique decoding capacity.
- 25 February 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (5) , 3409-3423
Key-Cast Over Networks
For a multi-source multi-terminal noiseless network, the multicast key-dissemination problem, here called the key-cast problem, involves the task of multicasting a (secret) key K from the network sources to its terminals. Unlike traditional communication, where messages must be delivered from source to destination(s) unchanged, key-cast is more flexible since key-cast need not require source reconstruction at destination nodes. Instead, the distributed key can be a mixture of sources from which the sources themselves may be unrecoverable. Key-cast (also known as secret key agreement) in memoryless networks has seen significant studies over the past decades. This work initiates the study of key-cast in noiseless networks, i.e., network coding, and addresses the similarities and differences between traditional forms of communication that require source reconstruction and the less constrained form of communication in the key-cast task. The study varies according to three criteria. The setting can be secure, in which case the shared key is not revealed to an eavesdropper (whose capabilities we constrain), or non-secure, in which case the key need not be hidden. The setting can have one or multiple source nodes capable of generating independent randomness to be used in the key generation process. And the setting can have one or multiple terminal sets, where the latter case is referred to as multiple key-cast. In multiple key-cast, one requires that terminals in each terminal set decode a different shared key. In the given settings, this work derives combinatorial conditions for key-cast and multiple key-cast and designs corresponding communication schemes. In addition, the study compares the key-cast rate with and without the restriction of source reconstruction that is needed in traditional forms of communication. Key-cast achieves a strict advantage in rate when source reconstruction is relaxed.
- 25 February 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (5) , 3409-3423
Key-Cast Over Networks
For a multi-source multi-terminal noiseless network, the multicast key-dissemination problem, here called the key-cast problem, involves the task of multicasting a (secret) key K from the network sources to its terminals. Unlike traditional communication, where messages must be delivered from source to destination(s) unchanged, key-cast is more flexible since key-cast need not require source reconstruction at destination nodes. Instead, the distributed key can be a mixture of sources from which the sources themselves may be unrecoverable. Key-cast (also known as secret key agreement) in memoryless networks has seen significant studies over the past decades. This work initiates the study of key-cast in noiseless networks, i.e., network coding, and addresses the similarities and differences between traditional forms of communication that require source reconstruction and the less constrained form of communication in the key-cast task. The study varies according to three criteria. The setting can be secure, in which case the shared key is not revealed to an eavesdropper (whose capabilities we constrain), or non-secure, in which case the key need not be hidden. The setting can have one or multiple source nodes capable of generating independent randomness to be used in the key generation process. And the setting can have one or multiple terminal sets, where the latter case is referred to as multiple key-cast. In multiple key-cast, one requires that terminals in each terminal set decode a different shared key. In the given settings, this work derives combinatorial conditions for key-cast and multiple key-cast and designs corresponding communication schemes. In addition, the study compares the key-cast rate with and without the restriction of source reconstruction that is needed in traditional forms of communication. Key-cast achieves a strict advantage in rate when source reconstruction is relaxed.
- Open Access
On Subset Retrieval and Group Testing Problems with Differential Privacy Constraints
This paper focuses on the design and analysis of privacy-preserving techniques for group testing and infection status retrieval. Our work is motivated by the need to provide accurate information on the status of disease spread among a group of individuals while protecting the privacy of the infection status of any single individual involved. The paper is motivated by practical scenarios, such as controlling the spread of infectious diseases, where individuals might be reluctant to participate in testing if their outcomes are not kept confidential. The paper makes the following contributions. First, we present a differential privacy framework for the subset retrieval problem, which focuses on sharing the infection status of individuals with administrators and decision-makers. We characterize the trade-off between the accuracy of subset retrieval and the degree of privacy guaranteed to the individuals. In particular, we establish tight lower and upper bounds on the achievable level of accuracy subject to the differential privacy constraints. We then formulate the differential privacy framework for the noisy group testing problem in which noise is added either before or after the pooling process. We establish a reduction between the private subset retrieval and noisy group testing problems and show that the converse and achievability schemes for subset retrieval carry over to differentially private group testing.
Open AccessOn Subset Retrieval and Group Testing Problems with Differential Privacy Constraints
This paper focuses on the design and analysis of privacy-preserving techniques for group testing and infection status retrieval. Our work is motivated by the need to provide accurate information on the status of disease spread among a group of individuals while protecting the privacy of the infection status of any single individual involved. The paper is motivated by practical scenarios, such as controlling the spread of infectious diseases, where individuals might be reluctant to participate in testing if their outcomes are not kept confidential. The paper makes the following contributions. First, we present a differential privacy framework for the subset retrieval problem, which focuses on sharing the infection status of individuals with administrators and decision-makers. We characterize the trade-off between the accuracy of subset retrieval and the degree of privacy guaranteed to the individuals. In particular, we establish tight lower and upper bounds on the achievable level of accuracy subject to the differential privacy constraints. We then formulate the differential privacy framework for the noisy group testing problem in which noise is added either before or after the pooling process. We establish a reduction between the private subset retrieval and noisy group testing problems and show that the converse and achievability schemes for subset retrieval carry over to differentially private group testing.
- Open Access
Bounds on Box Codes
Let $n_q(M,d)$ be the minimum length of a $q$-ary code of size $M$ and minimum distance $d$. Bounding $n_q(M,d)$ is a fundamental problem that lies at the heart of coding theory. This work considers a generalization $n^\bx_q(M,d)$ of $n_q(M,d)$ corresponding to codes in which codewords have \emph{protected} and \emph{unprotected} entries; where (analogs of) distance and of length are measured with respect to protected entries only. Such codes, here referred to as \emph{box codes}, have seen prior studies in the context of bipartite graph covering. Upper and lower bounds on $n^\bx_q(M,d)$ are presented.Open AccessBounds on Box Codes
Let $n_q(M,d)$ be the minimum length of a $q$-ary code of size $M$ and minimum distance $d$. Bounding $n_q(M,d)$ is a fundamental problem that lies at the heart of coding theory. This work considers a generalization $n^\bx_q(M,d)$ of $n_q(M,d)$ corresponding to codes in which codewords have \emph{protected} and \emph{unprotected} entries; where (analogs of) distance and of length are measured with respect to protected entries only. Such codes, here referred to as \emph{box codes}, have seen prior studies in the context of bipartite graph covering. Upper and lower bounds on $n^\bx_q(M,d)$ are presented. - Open Access
- 3 December 2024
- Published by Emerald Publishing in Foundations and Trends® in Communications and Information Theory
- Vol. 21 (3-4) , 300-588
Codes for Adversaries: Between Worst-Case and Average-Case Jamming
Over the last 70 years, information theory and coding has enabled communication technologies that have had an astounding impact on our lives. This is possible due to the match between encoding/decoding strategies and corresponding channel models. Traditional studies of channels have taken one of two extremes: Shannon-theoretic models are inherently average-case in which channel noise is governed by a memoryless stochastic process, whereas coding-theoretic (referred to as “Hamming”) models take a worst-case, adversarial, view of the noise. However, for several existing and emerging communication systems the Shannon/average-case view may be too optimistic, whereas the Hamming/worst-case view may be too pessimistic. This monograph takes up the challenge of studying adversarial channel models that lie between the Shannon and Hamming extremes.
- 3 December 2024
- Published by Emerald Publishing in Foundations and Trends® in Communications and Information Theory
- Vol. 21 (3-4) , 300-588
Open AccessCodes for Adversaries: Between Worst-Case and Average-Case Jamming
Over the last 70 years, information theory and coding has enabled communication technologies that have had an astounding impact on our lives. This is possible due to the match between encoding/decoding strategies and corresponding channel models. Traditional studies of channels have taken one of two extremes: Shannon-theoretic models are inherently average-case in which channel noise is governed by a memoryless stochastic process, whereas coding-theoretic (referred to as “Hamming”) models take a worst-case, adversarial, view of the noise. However, for several existing and emerging communication systems the Shannon/average-case view may be too optimistic, whereas the Hamming/worst-case view may be too pessimistic. This monograph takes up the challenge of studying adversarial channel models that lie between the Shannon and Hamming extremes.
- 26 April 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (7) , 4585-4598
Competitive Channel-Capacity
We consider communication over channels whose statistics are not known in full, but can be parameterized as a finite family of memoryless channels. A typical approach to address channel uncertainty is to design codes for the worst channel in the family, resulting in the well-known compound channel capacity. Although this approach is robust, it may suffer a significant loss of performance if the capacity-achieving distribution of the worst channel attains low rates over other channels. In this work, we cope with channel uncertainty through the lens of competitive analysis . The main idea is to optimize a relative metric that compares the performance of the designed code and a clairvoyant code that has access to the true channel. To allow communication rates that adapt to the channel at use, we consider rateless codes with a fixed number of message bits and random decoding times. We propose two competitive metrics: the competitive ratio between the expected rates of the two codes, and a regret defined as the difference between the expected rates. The competitive ratio, for instance, provides a percentage guarantee on the expected rate of the designed code when compared to the rate of the clairvoyant code that knows the channel at hand. Our main results are single-letter expressions for the optimal competitive-ratio and regret , expressed as a max-min or minmax optimization. Several examples illustrate the benefits of the competitive analysis approach to code design compared to the compound channel.
- 26 April 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (7) , 4585-4598
Competitive Channel-Capacity
We consider communication over channels whose statistics are not known in full, but can be parameterized as a finite family of memoryless channels. A typical approach to address channel uncertainty is to design codes for the worst channel in the family, resulting in the well-known compound channel capacity. Although this approach is robust, it may suffer a significant loss of performance if the capacity-achieving distribution of the worst channel attains low rates over other channels. In this work, we cope with channel uncertainty through the lens of competitive analysis . The main idea is to optimize a relative metric that compares the performance of the designed code and a clairvoyant code that has access to the true channel. To allow communication rates that adapt to the channel at use, we consider rateless codes with a fixed number of message bits and random decoding times. We propose two competitive metrics: the competitive ratio between the expected rates of the two codes, and a regret defined as the difference between the expected rates. The competitive ratio, for instance, provides a percentage guarantee on the expected rate of the designed code when compared to the rate of the clairvoyant code that knows the channel at hand. Our main results are single-letter expressions for the optimal competitive-ratio and regret , expressed as a max-min or minmax optimization. Several examples illustrate the benefits of the competitive analysis approach to code design compared to the compound channel.
- Open Access
Nobody Expects a Differential Equation: Minimum Energy-Per-Bit for the Gaussian Relay Channel with Rank-1 Linear Relaying
Motivated by the design of low-complexity low-power coding solutions for the Gaussian relay channel, this work presents an upper bound on the minimum energy-per-bit achievable on the Gaussian relay channel using rank-1 linear relaying. Our study addresses high-dimensional relay codes and presents bounds that outperform prior known bounds using 2-dimensional schemes. A novelty of our analysis ties the optimization problem at hand to the solution of a certain differential equation which, in turn, leads to a low energy-per-bit achievable scheme.
Open AccessNobody Expects a Differential Equation: Minimum Energy-Per-Bit for the Gaussian Relay Channel with Rank-1 Linear Relaying
Motivated by the design of low-complexity low-power coding solutions for the Gaussian relay channel, this work presents an upper bound on the minimum energy-per-bit achievable on the Gaussian relay channel using rank-1 linear relaying. Our study addresses high-dimensional relay codes and presents bounds that outperform prior known bounds using 2-dimensional schemes. A novelty of our analysis ties the optimization problem at hand to the solution of a certain differential equation which, in turn, leads to a low energy-per-bit achievable scheme.
- 10 January 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (6) , 3891-3902
Minimizing the Alphabet Size in Codes With Restricted Error Sets
This paper focuses on the study of the minimum possible alphabet size of codes in a generalized setting where the coding scheme is required to handle a pre-specified set of erasure or error patterns, naturally represented by a hypergraph. The need for such codes arises in many settings of practical interest, including wireless communication and flash memory systems. In many such settings, a smaller field size is achievable than that offered by MDS and other standard codes. We establish a connection between the minimum alphabet size of codes in this generalized setting and the combinatorial properties of the hypergraph that represents the pre-specified collection of erasure or error patterns. We also establish connections between error and erasure correcting codes in our generalized setting. Finally, we consider a variation of the problem that allows a small probability of decoding error and relate it to an approximate version of hypergraph coloring.
- 10 January 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (6) , 3891-3902
Minimizing the Alphabet Size in Codes With Restricted Error Sets
This paper focuses on the study of the minimum possible alphabet size of codes in a generalized setting where the coding scheme is required to handle a pre-specified set of erasure or error patterns, naturally represented by a hypergraph. The need for such codes arises in many settings of practical interest, including wireless communication and flash memory systems. In many such settings, a smaller field size is achievable than that offered by MDS and other standard codes. We establish a connection between the minimum alphabet size of codes in this generalized setting and the combinatorial properties of the hypergraph that represents the pre-specified collection of erasure or error patterns. We also establish connections between error and erasure correcting codes in our generalized setting. Finally, we consider a variation of the problem that allows a small probability of decoding error and relate it to an approximate version of hypergraph coloring.
- Open Access
Competitive Channel-Capacity
We consider communication over channels whose statistics are not known in full, but can be parameterized as a finite family of memoryless channels. A typical approach to address channel uncertainty is to design codes for the worst channel in the family, resulting in the well-known compound channel capacity. Although this approach is robust, it may suffer a significant loss of performance if the capacity-achieving distribution of the worst channel attains low rates over other channels. In this work, we cope with channel uncertainty through the lens of {\em competitive analysis}. The main idea is to optimize a relative metric that compares the performance of the designed code and a clairvoyant code that has access to the true channel. To allow communication rates that adapt to the channel at use, we consider rateless codes with a fixed number of message bits and random decoding times. We propose two competitive metrics: the competitive ratio between the expected rates of the two codes, and a regret defined as the difference between the expected rates. The competitive ratio, for instance, provides a percentage guarantee on the expected rate of the designed code when compared to the rate of the clairvoyant code that knows the channel at hand. Our main results are single-letter expressions for the optimal {\em competitive-ratio} and {\em regret}, expressed as a max-min or min-max optimization. Several examples illustrate the benefits of the competitive analysis approach to code design compared to the compound channel.
Open AccessCompetitive Channel-Capacity
We consider communication over channels whose statistics are not known in full, but can be parameterized as a finite family of memoryless channels. A typical approach to address channel uncertainty is to design codes for the worst channel in the family, resulting in the well-known compound channel capacity. Although this approach is robust, it may suffer a significant loss of performance if the capacity-achieving distribution of the worst channel attains low rates over other channels. In this work, we cope with channel uncertainty through the lens of {\em competitive analysis}. The main idea is to optimize a relative metric that compares the performance of the designed code and a clairvoyant code that has access to the true channel. To allow communication rates that adapt to the channel at use, we consider rateless codes with a fixed number of message bits and random decoding times. We propose two competitive metrics: the competitive ratio between the expected rates of the two codes, and a regret defined as the difference between the expected rates. The competitive ratio, for instance, provides a percentage guarantee on the expected rate of the designed code when compared to the rate of the clairvoyant code that knows the channel at hand. Our main results are single-letter expressions for the optimal {\em competitive-ratio} and {\em regret}, expressed as a max-min or min-max optimization. Several examples illustrate the benefits of the competitive analysis approach to code design compared to the compound channel.