Michael Langberg

Michael Langberg

Auto-generated profile, based on publicly available information

Michael Langberg

Department of Electrical Engineering, University at Buffalo, The State University of New York, Buffalo, NY, USA

Research Focus & Metrics

Academic Career Length

13Years (2014-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
10 October 2016 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
WHWentao Huang
Wentao Huang
MLMichael Langberg
Michael Langberg
JKJörg Kliewer
Jörg Kliewer
JBJehoshua Bruck
Jehoshua Bruck
A secret sharing scheme is a method to store information securely and reliably. Particularly, in a threshold secret sharing scheme, a secret is encoded into n shares, such that any set of at least t 1 shares suffice to decode the secret, and any set of at most t 2 <; t 1 shares reveal no information about the secret. Assuming that each party holds a share and a user wishes to decode the secret by receiving information from a set of parties; the question we study is how to minimize the amount of communication between the user and the parties. We show that the necessary amount of communication, termed “decoding bandwidth”, decreases as the number of parties that participate in decoding increases. We prove a tight lower bound on the decoding bandwidth, and construct secret sharing schemes achieving the bound. Particularly, we design a scheme that achieves the optimal decoding bandwidth when d parties participate in decoding, universally for all t 1 ≤ d ≤ n. The scheme is based on a generalization of Shamir's secret sharing scheme and preserves its simplicity and efficiency. In addition, we consider the setting of secure distributed storage where the proposed communication efficient secret sharing schemes not only improve decoding bandwidth but further improve disk access complexity during decoding.

14 May 2019 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
BDBikash Kumar Dey
Bikash Kumar Dey
SJSidharth Jaggi
Sidharth Jaggi
MLMichael Langberg
Michael Langberg
We consider a communication problem in which a sender, Alice, wishes to communicate with a receiver, Bob, over a channel controlled by an adversarial jammer, James, who is myopic. Specifically, for blocklength n, the codeword Xn transmitted by Alice is corrupted by James who must base his adversarial decisions (of which locations of Xn to corrupt and how to corrupt them) on the non-causal observation Zn of Xn obtained through a noisy memoryless channel. More specifically, our communication model may be described by two channels. A memoryless channel pZjX from Alice to James, and an Arbitrarily Varying Channel from Alice to Bob, pY jXS governed by a state Sn determined by James. In standard adversarial channels the states Sn may depend on the codeword Xn, but in our setting Sn depends non-causally only on James’s view Zn. We present upper and lower bounds on the capacity of myopic channels. For a number of special cases of interest we show that our bounds are tight. We then extend our results to the setting of secure communication, in which we require that the transmitted message remains secret from James. For example, we show that if (i) James may flip at most a p fraction of the bits communicated between Alice and Bob, and (ii) James views Xn through a binary symmetric channel with crossover probability q, then once James is “sufficiently myopic” (in this case, when p < 0:5 and H(q) > H(p)), then the optimal communication rate is that of an adversary who is “blind” (that is, an adversary that does not have any knowledge of Xn at all), which is 1.. H(p) for standard communication, and H(q)..H(p) for secure communication. A similar phenomenon exists for more general models of communication.

23 November 2020 in IEEE Transactions on Signal Processing
Verified
Journal Article
Closed access
HKHossein Kamrani
Hossein Kamrani
AAAlireza Zolghadr Asli
Alireza Zolghadr Asli
PMPanos P. Markopoulos
Panos P. Markopoulos
MLMichael Langberg
Michael Langberg
Dimitris PadosDimitris Pados
Dimitris Pados
GKGeorge N. Karystinos
George N. Karystinos
Standard Principal-Component Analysis (PCA) is known to be sensitive to outliers among the processed data. On the other hand, L1-norm-based PCA (L1-PCA) exhibits sturdy resistance against outliers, while it performs similar to standard PCA when applied to nominal or smoothly corrupted data [1]. Exact calculation of the K L1-norm Principal Components (L1-PCs) of a rank-r datamatrix X ∈ℝ D×N costs O(N (r-1)K+1 ) [1], [2]. In this work, we present reduced-rank L1-PCA (RR L1-PCA): a hybrid approach that approximates the K L1-PCs of X by the L1-PCs of its L2-norm-based rank-d approximation (d ≤ r), calculable exactly with reduced complexity O(N (d-1)K+1 ). The proposed method combines the denoising capabilities and low computation cost of standard PCA with the outlier-resistance of L1-PCA. RR L1-PCA is accompanied by formal performance guarantees as well as thorough numerical studies that corroborate its computational and corruption resistance merits.

13 October 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
MLMichael Langberg
Michael Langberg
MSMoshe Schwartz
Moshe Schwartz
EYEitan Yaakobi
Eitan Yaakobi
We consider the communication of information in the presence of synchronization errors. Specifically, we consider permutation channels in which a transmitted codeword x = (x 1 , ... , x n ) is corrupted by a permutation π ∈ S n to yield the received wordy = (y 1 , . . . , y n ), where y i = x π(i) . We initiate the study of worst case (or zero-error) communication over permutation channels that distort the information by applying permutations π, which are limited to displacing any symbol by at most r locations, i.e., permutations π with weight at most r in the ℓ ∞ -metric. We present direct and recursive constructions, as well as bounds on the rate of such channels for binary and general alphabets. Specific attention is given to the case of r = 1.

1 December 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
PNParham Noorzad
Parham Noorzad
MEMichelle Effros
Michelle Effros
MLMichael Langberg
Michael Langberg
Cooperation strategies allow communication devices to work together to improve network capacity. Consider a network consisting of k encoders, a multiple access channel (MAC), a decoder, and a node, referred to as a “cooperation facilitator” (CF), that is connected to each encoder via a pair of rate-limited links, with one link going from the encoder to the CF and the other link going back. Let the “cooperation rate” be the total outgoing rate of the CF. This work demonstrates the existence of a class of MACs where the ratio of the sum-capacity gain to cooperation rate tends to infinity as the cooperation rate tends to zero. For any k ≥ 2, examples of channels in this class include the k-user binary adder MAC and the k-user Gaussian MAC.

29 March 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
WHWentao Huang
Wentao Huang
THTracey Ho
Tracey Ho
MLMichael Langberg
Michael Langberg
JKJörg Kliewer
Jörg Kliewer
This paper reduces multiple-unicast network coding to single-unicast secure network coding and single-unicast network error correction. Specifically, we present reductions that map an arbitrary multiple-unicast network coding instance to a unicast secure network coding instance in which at most one link is eavesdropped, or a unicast network error correction instance in which at most one link is erroneous, such that a rate tuple is achievable in the multiple-unicast network coding instance if and only if a corresponding rate is achievable in the unicast secure network coding instance, or in the unicast network error correction instance. Conversely, we show that an arbitrary unicast secure network coding instance in which at most one link is eavesdropped can be reduced back to a multiple-unicast network coding instance. In addition, we show that the capacity of a unicast network error correction instance in general is not (exactly) achievable.