Parimal Parag is an Assistant Professor in the Department of Electrical Communication Engineering at Indian Institute of Science, Bengaluru. Prior to that, he was a senior system engineer (R&D) at ASSIA Inc. in Redwood City from 2011 to 2014. He received a Ph.D. degree from the Texas A&M University in 2011, the M.Tech. and B.Tech. degrees in 2004 from Indian Institute of Technology Madras, all in electrical engineering. His research interests lie in the design and analysis of large scale distributed systems. He was a co-author of the 2018 IEEE ISIT student best paper, and a recipient of the 2017 early career award from the Science and Engineering Research Board.
Nikhil Karamchandani is an assistant professor at the Department of Electrical Engineering, IIT Bombay. He received the Ph.D. degree from the Department of Electrical and Computer Engineering, University of California at San Diego, in 2011. From 2011 to 2014, he was a post-doctoral Scholar with the University of California at Los Angeles and the Information Theory and Applications (ITA) Center, University of California at San Diego. His research interests include networks, information theory, and online learning. He received the California Institute for Telecommunications and Information Technology (CalIT2) Fellowship in 2005, the INSPIRE Faculty Fellowship in 2015, and the Best Paper Award at COMSNETS 2017.
Krishna Jagannathan obtained his B. Tech. in Electrical Engineering from IIT Madras in 2004, and the S.M. and Ph.D. degrees in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology (MIT) in 2006 and 2010 respectively. During 2010-2011, he was a visiting post-doctoral scholar in Computing and Mathematical Sciences at Caltech, and an off-campus post-doctoral fellow at MIT. Since November 2011, he has been with the Department of Electrical Engineering, IIT Madras, where he is currently an associate professor. He worked as a consultant at the Mathematical Sciences Research Center, Bell Laboratories, Murray Hill, NJ in 2005, and as an engineering intern at Qualcomm, Campbell, CA in 2007. His research interests lie in the stochastic modeling and analysis of communication networks, transportation networks, network control, and queuing theory.
Abstract: Successive cancellation list decoding of polar codes provides very good performance for short to moderate block lengths. However, the list size required to approach the performance of maximum-likelihood decoding is still not well understood theoretically. This work identifies information-theoretic quantities that are closely related to this required list size. It also provides a natural approximation for these quantities that can be computed efficiently even for very long codes. Simulation results are provided for the binary erasure channel as well as the binary-input additive white Gaussian noise channel.
This is joint work with Mustafa Cemil Coşkun.
I am a postdoctoral researcher at the Technical University of Munich. I received the Diploma degree in computer and communication engineering from the Lebanese University, Faculty of Engineering, Roumieh, Lebanon in 2013 and the M.S. degree from the Lebanese University, Doctoral school, Tripoli, Lebanon in 2014. I received my Ph.D degree in electrical engineering from Rutgers University, New Jersey, in January 2020. My research interests are in the broad area of information theory and coding theory with a focus on coding for information theoretically secure distributed systems with application to machine learning.
Abstract: We consider the private coded computing setting in which a master server possesses confidential data and wants to run intensive linear computations (matrix-matrix multiplication) on it. The master distributes these computations redundantly to several worker machines. After receiving enough responses from the workers, the master obtains the original computation. However, the data must be kept private from the individual workers, in an information theoretic sense. The compute time at the workers are different and time-varying due to different workloads, network and computing power. We are interested in private coding schemes that can guarantee privacy, reduce the aggregate delay experienced by the master, and assign computations that are proportional to each worker’s compute time.
Towards that goal, I will introduce a new family of codes, called PRAC, which can guarantee the desired properties when only one of the input matrices is private. I will introduce RPM3, a generalization of PRAC for the case where both input matrices are private. I will discuss the construction of these codes and present theoretical guarantees on their performance under exponential delay model. Then, I will present results from experiments we ran on Android phones and tablets. I will conclude with some problems that remain open.
Sreeram Kannan is currently an assistant professor at University of Washington, Seattle. He was a postdoctoral scholar at University of California, Berkeley between 2012-2014 before which he received his Ph.D. in Electrical Engineering and M.S. in mathematics from the University of Illinois Urbana Champaign. He is a recipient of the 2019 UW ECE outstanding teaching award, 2017 NSF Faculty Early CAREER award, the 2013 Van Valkenburg outstanding dissertation award from UIUC, a co-recipient of the 2010 Qualcomm Cognitive Radio Contest first prize, a recipient of 2010 Qualcomm (CTO) Roberto Padovani outstanding intern award, a recipient of the SVC Aiya medal from the Indian Institute of Science, 2008, and a co-recipient of Intel India Student Research Contest first prize, 2006. His research interests include the applications of information theory and learning to blockchains, computational biology and wireless networks.
Abstract: One important application of codes in blockchains is in information dispersal, where a client wants to disperse coded information to a set of servers. However, in such applications it is possible that the data is inconsistently coded by the client dispersing the data. In this paper, we propose coded Merkle tree (CMT), a novel hash accumulator that provides the ability for a node to provide a short proof that the data was inconsistently coded. A CMT is constructed using a family of sparse erasure codes on each layer, and is recovered by iteratively applying a peeling-decoding technique that enables a compact proof for incorrect coding on any layer. We show that such structures have natural applications in guaranteeing data availability in blockchains. Our algorithm enables any node to verify the full availability of any data block (of size b) generated by the system by just downloading a Θ(1) byte block hash commitment and randomly sampling Θ(log b) bytes, where b is the size of the data block. With the help of only one connected honest node in the system, our method also allows any node to verify any tampering of the coded Merkle tree by just downloading Θ(log b) bytes. We provide a modular library for CMT in Rust and Python and demonstrate its efficacy inside the Parity Bitcoin client. Finally, we point out open problems as well as other potential applications of codes in blockchains. Reference: https://arxiv.org/abs/1910.01247
Arun Padakandla was a postdoctoral research fellow with the NSF Center for Science of Information at Purdue Univ. from 2015-2018. Since 2018, he has been on the faculty of the Dept. of EECS, Univ. of Tennessee at Knoxville. His research interests lie in classical and quantum information theory.
Abstract: In this talk, we highlight a connection between the classical works of Shannon [1948] and Witsenhausen [1975 SIAM Disc Math]. This connection suggests a tension in the choice of the optimal block-length in certain multi-terminal communication problems involving distributed correlated sources. Building on this observation, we present a new coding scheme for the problems of communicating correlated sources over multiple access and interference channels. The proposed coding scheme has been proven to yield a new set of sufficient conditions for both problems that are (i) subsumed within the current known and (ii) strictly weaker for identified examples. Going further, we study the problem of noninteractive simulation of joint distribution from a decidability viewpoint. The above mentioned connection can be used to prove stronger results than those currently known.
Gauri Joshi is an assistant professor in the ECE department at Carnegie Mellon University since September 2017. Previously, she worked as a Research Staff Member at IBM T. J. Watson Research Center. Gauri completed her Ph.D. from MIT EECS in June 2016, advised by Prof. Gregory Wornell. She received her B.Tech and M.Tech in Electrical Engineering from the Indian Institute of Technology (IIT) Bombay in 2010. Her awards and honors include the NSF CRII Award (2018), IBM Faculty Research Award (2017), Best Thesis Prize in Computer science at MIT (2012), Institute Gold Medal of IIT Bombay (2010), and the Claude Shannon Research Assistantship (2015-16).
Abstract: Large-scale machine learning and data mining applications require computer systems to perform massive matrix-vector and matrix-matrix multiplication operations that need to be parallelized across multiple nodes. The presence of straggling nodes -- computing nodes that unpredictably slowdown or fail -- is a major bottleneck in such distributed computations. Ideal load balancing strategies that dynamically allocate more tasks to faster nodes require knowledge or monitoring of node speeds as well as the ability to quickly move data. Recently proposed fixed-rate erasure coding strategies can handle unpredictable node slowdown, but they ignore partial work done by straggling nodes thus resulting in a lot of redundant computation. We propose a \emph{rateless fountain coding} strategy that achieves the best of both worlds -- we prove that its latency is asymptotically equal to ideal load balancing, and it performs asymptotically zero redundant computations. Our idea is to create linear combinations of the m rows of the matrix and assign these encoded rows to different worker nodes. The original matrix-vector product can be decoded as soon as slightly more than m row-vector products are collectively finished by the nodes. We conduct experiments in three computing environments: local parallel computing, Amazon EC2, and Amazon Lambda, which show that rateless coding gives as much as 3× speed-up over uncoded schemes.
Pradeep Kiran Sarvepalli is an Associate Professor at the Indian Institute of Technology Madras. He graduated with a PhD. in Computer Science from Texas A&M University. Previously he was a Postdoctoral Fellow in University of British Columbia and Georgia Institute of Technology. He also worked as an IC Design Engineer in Texas Instruments India, Bangalore. His research interests are classical and quantum error correcting codes, quantum cryptography, quantum computation, and distributed storage.
Abstract: Quantum error correcting codes are essential for protecting and processing quantum information in the presence of noise. In this talk I will give a brief introduction to a class of quantum codes in three dimensions called 3D toric codes. I will then present some recent results on efficiently decoding of 3D toric codes over arbitrary lattices. These results can be used to decode other topological codes in 3D such as the color codes and gauge color codes. The talk will not assume any background in quantum error correction.
(Joint work with Arun Aloshious)
