The general theme of our research is to develop innovative approaches to characterize and achieve the fundamental limits of reliable, trustworthy, and verifiable distributed systems, including distributed computing and machine learning, content delivery networks, and distributed ledgers (blockchains). 

Secure and Private Distributed Computing 

Distributed computing raises a long list of challenges, including the heavy load of communication, the existence of stragglers, information leakage to external servers, etc. We took the first step toward understanding distributed computing from an information-theoretic perspective. We characterized the communication-computation trade-off for one of the most popular general-purpose settings, adopted in MapReduce and Apache Spark. In addition, we developed a coding approach that achieves the optimum trade-off and significantly reduces the communication load. While the benefits of coding in dealing with the stragglers in linear and bilinear computations, such as distributed massive matrix multiplications, were studied in the 80’s , designing the optimum code remained an open problem. In this regard, we developed a creative polynomial-based coding technique with optimum robustness against stragglers.

In this direction, we also radically extended secure multi-party computation (MPC) to handle massive computations, a subject that has been overlooked in the field. We also developed efficient and practical approaches to private machine learning, and straggler-resistant massive approximate computation, particularly for machine learning applications.

Coded Caching

The conventional approach to reducing the traffic load is to exploit the memories distributed across the network to duplicate (or cache) the popular content. Today’s content delivery networks are designed and optimized to increase hit rate, i.e., the chance of providing requested content from a local cache. We proved that this intuitive approach is substantially inefficient. We presented the first information-theoretic fundamental trade-off between the communication rate and cache size

for distributed cache networks and proved its optimality. To achieve optimum performance, we introduced the concept of coded caching, which relies on planning and exploiting the cached content to create particular coding opportunities. The gain offered by coded caching scales with the size of the network, which makes it even more attractive for overwhelmingly growing networks.

To translate this idea into practice, and in interaction with the business division of Nokia, we further extended the concept of coded caching to support various real-world scenarios. In particular, we addressed the cases where file popularities are non-uniform and time-varying, and the demands are asynchronous and delay-sensitive. We also generalized the proposed scheme to hierarchical cache networks or cache-aided wireless channels. Our practical implementations (Demo) demonstrated at the company’s showcases intrigued many visitors and business partners.

Interference Management using Outdated Channel State Information

The communication delay in distributed systems can significantly affect the network’s performance. An example of such systems is multi-user communication networks, where interference management techniques rely on up-to-date channel state information (CSI). However, estimating and circulating this knowledge is subject to some delay, making it outdated. There was an unquestioned belief that outdated CSI, uncorrelated with the current one, is entirely useless. We developed an innovative approach, leveraging the outdated CSI, to improve the throughput of a K-user (Broadcast) wireless network by a factor of K/log(K). Our proposed approach has initiated a new way to utilize outdated CSI, which has been extensively explored for various network settings.

Interference Alignment

Competition for communication medium is an inherent attribute of distributed systems, where concurrent interactions create interference on each other. In the absence of collaborative interference management, the communication links were conventionally scheduled in different orthogonal dimensions. In [9], we disproved this prevailing belief and introduced a fundamentally new approach to managing interference. Our so-called interference alignment (IA) scheme provides interference-free communication without splitting the network resources and sacrificing the throughput. This is done by aligning different interference contributions at each receiver to minimize their overall footprint. The surprising consequence is that when a new link starts communicating over the shared medium, it ideally will not affect the rate of the other links. Over the past few years, interference alignment has been one of the central topics of research in the field, with significant implications beyond interference management in distributed storage, computation, and private information retrieval.

Visit Mohammad Ali Maddah-Ali's Experts@Minnesota profile page

Education

Ph.D., Department of Electrical and Computer Engineering, University of Waterloo, Canada

Professional Background

From 2007 to 2008, I was with the Wireless Technology Laboratories, Nortel Networks, Ottawa, ON, Canada. From 2008 to 2010, I was a Postdoctoral Fellow at the Department of Electrical Engineering and Computer Sciences, University of California at Berkeley. From Sept. 2010 to Sept. 2020, I was a Communication Research Scientist at Nokia Bell Labs, Holmdel, NJ, USA.

I also served as an associate editor of the IEEE Transactions on Information Theory 2019-2022 and a lead editor for the IEEE Journal on Selected Areas in Information Theory. I am currently a member of the award committee of the IEEE Information Theory Society.

Scientific & Professional Societies

Honors and Awards

• 2023 IEEE Fellow, Class of 2023, Citation: “for contributions to information theory for interference management, coded caching and computing”

• 2017 IEEE Jack Keil Wolf IEEE International Symposium on Information Theory Student Paper Award

• 2016 IEEE Information Theory Society Paper Award

• 2015 IEEE Communications Society & Information Theory Society Joint Paper Award

• 2014 Best Paper Award, IEEE International Conference on Communications (ICC)

• 2010 Honorable Mention for Inventing the Idea of Interference Alignment by the IEEE Society of Information Theory, 2010

Selected Publications

T. Jahani-Nezhad and M.A. Maddah-Ali, “Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing,” arXiv:2009.08327 [cs.IT, cs.DC, cs.LG], IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume: 45, Issue: 1, January 2023.

T. Jahani-Nezhad, M.A. Maddah-Ali, S. Li, and G. Caire, “SwiftAgg+: Achieving Asymptotically Optimal Communication Loads in Secure Aggregation for Federated Learning,” arXiv:2203.13060 [cs.IT, cs.DC, cs.LG], Accepted for IEEE Journal on Selected Areas in Communications, Dec. 2022.

T. Jahani-Nezhad and M.A. Maddah-Ali, “Optimal Communication-Computation Trade-Off in Heterogeneous Gradient Coding,” IEEE Journal on Selected Areas in Information Theory (JSAIT), Volume: 2, Issue: 3, September 2021.

 A. Rahimi and M. A. Maddah-Ali, “Multi-Party Proof Generation in QAP-based zk-SNARKs,” IEEE Journal on Selected Areas in Information Theory (JSAIT), Volume: 2, Issue: 3, September 2021.

  A. Khalesi, M. Mirmohseni, and M.A. Maddah-Ali, “The Capacity Region of Distributed Multi-User Secret Sharing,” IEEE Journal on Selected Areas in Information Theory (JSAIT), Volume: 2, Issue: 3, September 2021.

S.R. Hosseini Najarkolaei, M.A. Maddah-Ali, and M.R. Aref, ‘Coded Secure Multi-Party Computation for Massive Matrices with Adversarial Nodes,” Submitted to IEEE Transactions on Information Theory, (revised) Dec. 2022.

T. Jahani-Nezhad and M. A. Maddah-Ali, “CodedSketch: A Coding Scheme for Distributed Computation of Approximated Matrix Multiplication,” arXiv:1510.06121 [cs.IT], IEEE Transactions on Information Theory, Volume: 67, Issue: 6, June 2021.

J8.  S. Sahraei, M. A. Maddah-Ali, and S. Avestimehr, “Interactive Verifiable Polynomial Evaluation,” IEEE Journal on Selected Areas in Information Theory (JSAIT), Volume: 2, Issue: 1, March 2021.

 S. Jafari, P. Shariatpanahi, and M.A. Maddah-Ali, “ Private Information Retrieval for a Multi-Message Scenario with Private Side Information,” IEEE Transactions on Communications, Volume: 69, Issue: 5, May 2021.

 S. Li, R. Elkordy, M.A. Maddah-Ali, and S. Avestimehr, “Compressed Coded Distributed Computing,” IEEE Transactions on Communications, Volume: 69, Issue: 5, May 2021.

E. Tohidi, S. Parsaeefard, M.A. Maddah-Ali, and B.H. Khalaj, and A. Leon- Garcia, “Near-Optimal Robust Virtual Controller Placement in 5G Software Defined Networks,” IEEE Transactions on Network Science and Engineering, Volume: 8, Issue: 2, April-June 2021

 B. Tahmasebi, M. A. Maddah-Ali, and S. A. Motahari, “The Capacity of Associated Subsequence Retrieval,” IEEE Transactions on Information Theory, Volume: 67, Issue: 2, February 2021

N. Abadi Khooshemehr and M. Ali Maddah-Ali, “Fundamental Limits of Distributed Encoding,” arXiv:2004.00811 [cs.IT] IEEE Transactions on Information Theory, Volume: 67, Issue: 12, December 2021.

B. Tahmasebi and M. A. Maddah-Ali, “Private Sequential Computation,” arXiv:1908.01204 [cs.IT], Submitted to IEEE Transactions on Information Theory, June 2020.

H. Akbari Nodehi, and M.A. MaddahAli, “Secure Coded Multi-Party Computation for Massive Matrix Operations,” arXiv:1908.04255 [cs.IT] Accepted for IEEE Transactions on Information Theory, Volume: 67, Issue: 4, April 2021. May 2018.

Q. Yu, M.A. Maddah-Ali, and S. Avestimehr, “Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding,” IEEE Transactions on Information Theory, Volume: 66, Issue: 3, March 2020.

B. Kananian, M.A. Maddah-Ali, and B.H. Khalaj, “K-User Interference Channel with Backhaul Cooperation: DoF vs. Backhaul Load Trade-Off,” IEEE Transactions on Information Theory, Nov. 2019.

M.A. Maddah-Ali and U. Niesen, “Cache-Aided Interference Channels,” IEEE Transactions on Information Theory, p.p.1714 – 1724, March 2019.

N. NaderiAlizadeh, M.A. Maddah-Ali, and S. Avestimehr, “Cache-Aided Interference Management in Wireless Cellular Networks,” Accepted for IEEE Transactions on Communications, January 2019.

Q. Yu, M.A. Maddah-Ali, and S. Avestimehr, “Characterizing the Rate-Memory Tradeoff in Cache Networks within a Factor of 2,” IEEE Transactions on Information Theory, p.p. 647– 663 January 2019.

Y. Yang, S. Chen, M.A. Maddah-Ali, P. Grover, and S. Kar, “Fast Temporal Path Localization on Graphs via Multiscale Viterbi Decoding,” IEEE Transactions on Signal Processing, p.p. 5588 – 5603, Volume: 66, Issue: 21, November 2018.

N. Yaghmaie, M.A. Maddah-Ali, H.F. Jelinek, and F. Mazrbanrad, “Dynamic signal quality index for electrocardiograms,” Physiological Measurement, Volume 39, Number 10, October 2018.

B. Tahmasebi, M.A. Maddah-Ali, S. Parsaeefard, and B.H. Khalaj, “Optimum Transmission Delay for Function Computation in NFV-Based Networks: The Role of Network Coding and Redundant Computing,” IEEE Journal on Selected Areas in Communications, p.p. 2233 - 2245, Volume: 36, Issue: 10, Oct. 2018.

M.A. Tahmasbi Nejad, S. Parsaeefard, M.A. Maddah-Ali, T. Mahmoodi, B.H. Khalaj “vSPACE: VNF Simultaneous Placement, Admission Control, and Embedding,” IEEE Journal on Selected Areas in Communications, p.p. 542 - 557, Volume: 36 , Issue: 3, March 2018.

Q. Yu, M.A. Maddah-Ali, and S. Avestimehr, “The Exact Rate-Memory Tradeoff for Caching with Uncoded Prefetching,” arXiv:1609.07817 [cs.IT], IEEE Transactions on Information Theory, p.p. 1281 - 1296, Volume: 64, Issue: 2, Feb. 2018.

S. Li, M.A. Maddah-Ali, Q. Yu, and S. Avestimehr, “A Fundamental Tradeoff Between Computation and Communication in Distributed Computing,” IEEE Transactions on Information Theory, p.p. 109 - 128, Volume: 64, Issue: 1, January 2018.

S. Li, Q. Yu, M.A. Maddah-Ali, and S. Avestimehr, “A Scalable Framework for Wireless Distributed Computing,” IEEE/ACM Transactions on Networking, p.p: 2643 – 2654, Volume: 25, Issue: 5, Oct. 2017.

U. Niesen and M.A. Maddah-Ali, “Coded Caching With Nonuniform Demands,” IEEE Transactions on Information Theory, p.p. 1146 - 1158, Volume: 63, Issue: 2, Feb. 2017.

 N. NaderiAlizadeh, M.A. Maddah-Ali, and S. Avestimehr, “Fundamental Limits of Cache-Aided Interference Management,” arXiv:1602.04207 [cs.IT], IEEE Transactions on Information Theory, p.p. 3092 - 3107, Volume: 63, Issue: 5, May 2017.

S. Li, M.A. Maddah-Ali, and S. Avestimehr, “Coding for Distributed Fog Computing,” IEEE Communications Magazine, p.p. 34 - 40m Volume: 55, Issue: 4, April 2017.

D. Kao, M. Maddah-Ali, S. Avestimehr, “Blind Index Coding,” arXiv:1504.06018 [cs.IT], IEEE Transactions on Information Theory, p.p. 2076 - 2097, Volume: 63, Issue: 4, April 2017.

A. Vahid, M. Maddah-Ali, S. Avestimehr, “Approximate Capacity Region of the MISO Broadcast Channels with Delayed CSIT,” IEEE Transactions on Communications, p.p.: 2913 - 2924, Volume: 64, Issue: 7, July 2016.

M.A. Maddah-Ali and U. Niesen, “Coding for Caching: Fundamental Limits And Practical Challenges,” IEEE Communications Magazine, p.p 23 - 29, Volume: 54, Issue: 8, August 2016.

N. Karamchandani, U. Niesen, M.A. Maddah-Ali, and S. Diggavi “Hierarchical Coded Caching,” arXiv:1403.7007 [cs.IT], IEEE Transactions on Information Theory, p.p. 3212 - 3229, Volume: 62, Issue: 6, June 2016.

R. Pedarsani, M.A. Maddah-Ali, U. Niesen, “Online Coded Caching,” arXiv:1311.3646 [cs.IT], IEEE/ACM Transactions on Networking, p.p. 836-845, Volume 24, Issue
2, April 2016

V. Ntranos, M.A. Maddah-Ali, and G. Caire, “Cellular Interference Alignment: Omni-Directional Antennas and Asymmetric Configurations,” arXiv:1404.6512 [cs.IT], IEEE Transactions on Information Theory, pp. 6663 – 6679, Volume: 61, Issue: 12, December 2015.

M.A. Maddah-Ali and U. Niesen, “Decentralized Coded Caching Attains Order-Optimal Memory-Rate Tradeoff,” arXiv:1301.5848 [cs.IT], IEEE/ACM Transactions on Networking, Volume 23, Issue 4, pp. 1029 – 1040, August 2015.

V. Ntranos, M.A. Maddah-Ali, and G. Caire, “Cellular Interference Alignment,” arXiv:1402.3119 [cs.IT], IEEE Transactions on Information Theory, p.p.: 1194 – 1217, Volume: 61, Issue: 3, March 2015.

V. Ntranos, M.A. Maddah-Ali, and G. Caire, “Cooperation Alignment for Distributed Interference Management,” arXiv:1510.01367 [cs.IT], Submitted to IEEE Transactions on Information Theory, October 2015.

A. Vahid, M.A. Maddah-Ali, and S. Avestimehr, “Capacity Results for Binary Fading Interference Channels with Delayed CSIT,” arXiv:1301.5309 [cs.IT], IEEE Transactions on Information Theory, pp. 6093 - 6130, Volume: 60, Issue: 10, Oct. 2014.

A.S. Motahari, S. Oveis-Gharan, M.A. Maddah-Ali, and A.K. Khandani, “Real Interference Alignment: Exploiting the Potential of Single Antenna Systems,” arXiv:0908.2282 [cs.IT], IEEE Transactions on Information Theory, Volume 60, Issue 8, pp. 4799 – 4810, August 2014.

M.A. Maddah-Ali and U. Niesen, “Fundamental Limits of Caching,” arXiv:1209.5807 [cs.IT], IEEE Transactions on Information Theory, Volume 60, Issue 5, pp. 2856- 2867, May 2014 (received the 2016 IEEE Information Theory Society Paper Award).

A. Vahid, M.A. Maddah-Ali, and S. Avestimehr, “Binary Fading Interference Channel with No CSIT,” arXiv:1405.0203 [cs.IT], Submitted to IEEE Transactions on Information Theory, April 2014.

U. Niesen and M.A. Maddah-Ali, “Interference Alignment: From Degrees-of-Freedom to Constant-Gap Capacity Approximations,” IEEE Transactions on Information Theory, Volume 59, Issue 8, pp. 4855 – 4888, August 2013.

M.A. Maddah-Ali and D. Tse, “Completely Stale Transmitter Channel State Information is Still Very Useful,” IEEE Transactions on Information Theory, Volume 58, Issue 7, pp. 4418 - 4431, July 2012 (received the 2015 IEEE Communications Society & Information Theory Society Joint Paper Award.).

M.A. Maddah-Ali, S.A. Motarahi, and A.K. Khandani, “Communication Over MIMO X Channels: Interference Alignment, Decomposition, and Performance Analysis,” IEEE Transactions on Information Theory, Volume 54, Issue 8, pp. 3457 – 3470, August 2008 (received mention from IEEE Information Theory Society for introducing interference alignment).

M.A. Maddah-Ali, M. Ansari, and A.K. Khandani, “Broadcast in MIMO Systems Based on a Generalized QR Decomposition: Signaling and Performance Analysis,” IEEE Transactions on Information Theory, Volume 54, Issue 3, pp. 1124 – 1138, March 2008.

M.A. Maddah-Ali, A. Mobasher, and A.K. Khandani, “Fairness in Multiuser Systems with Polymatroid Capacity Region,” IEEE Transactions on Information Theory, Volume 55, Issue 5, pp. 2128 – 2138, May 2009.

M. Ansari, M.A. Maddah-Ali, and A.K. Khandani, “On the Capacity of Time-Varying Channels with Periodic Feedback,” IEEE Transactions on Information Theory, Volume 53, Issue 8, pp. 2910 – 2915, August 2007.

M. Ebrahimi, M.A. Maddah-Ali, and A.K. Khandani, “Throughput Scaling Laws for Wireless Networks With Fading Channels,” IEEE Transactions on Information Theory, Volume 53, Issue 11, pp. 4250 – 4254, November 2007.

M.A. Maddah-Ali and A.K. Khandani, “A New Non-Orthogonal Space-Time Code with Low Decoding Complexity,” IEEE Transactions on Wireless Communications, Volume 5, Issue 5, pp. 1115 – 1121, May 2006.