HyWIT 2020

Speaker	Date & Time (IST)	Topic	Webex Link
Govinda Kamath	14th September 6:00 - 7:30 PM	Spectral Algorithms and Multiarmed-Bandits in Pairwise Sequence Alignment	Completed
Petros Elia	15th September 6:00 - 7:30 PM	Is Caching the Missing Link in Wireless Communications?	Completed
Andreas Dotzler	18th September 6:00 - 7:30 PM	Content Distribution with Coded Caching - Applications, System Design, and Implementation Challenges	Completed
Han Mao Kiah	21st September 6:00 - 7:30 PM	Balancing à la Knuth for DNA-based Data Storage	Completed
Sidharth Jaggi	23rd September 6:00 - 7:30 PM	Communication in the Presence of Adversarial Jamming: The Curious Case of the Erasure Channel	Completed
Sandip Sarkar	25th September 9:00 - 10:30 PM	Evolution of Modulation and Coding for Current Wireless Systems	Completed
Navin Kashyap	28th September 6:00 - 7:30 PM	Sampling from Probability Distributions on Lattices	Click here to join talk
Harshan Jagadeesh	30th September 6:00 - 7:30 PM	Practical Strategies for Synthesizing Shared Secret Keys at the Physical Layer in Wireless Networks	Click here to join talk
Son Hoang Dau	02nd October 6:00 - 7:30 PM	On the Problem of Repairing Reed-Solomon Codes	Click here to join talk

Details of the talks

Title: Spectral Algorithms and Multiarmed-Bandits in Pairwise Sequence Alignment
Speaker: Dr. Govinda Kamath, Microsoft Research, Cambridge
Abstract: Pairwise sequence alignment is often a computational bottleneck in genomic analysis pipelines, particularly in the context of third-generation sequencing technologies. To speed up this process, k-mer Jaccard similarities are often used as a proxy for alignment size to filter pairs of reads, and min-hashes are employed to efficiently estimate these similarities. However, when the k-mer distribution of a dataset is significantly non-uniform (e.g., due to GC biases or repeats), Jaccard similarity is no longer a good proxy for alignment size. We introduce a min-hash-based approach to estimate alignment sizes called Spectral Jaccard Similarity, which naturally accounts for uneven k-mer distributions. The Spectral Jaccard Similarity is computed by performing a singular value decomposition on a min-hash collision matrix. We show that this metric provides significantly better estimates for alignment sizes.We then explore the use of adaptivity to further speed up the estimation procedure. This involves using a multi-armed bandit algorithm to adaptively refine the alignment score estimates only for read pairs that are likely to have significant alignments. The resulting algorithm repeatedly performs a spectral decomposition of adaptively chosen submatrices. We show that adaptivity allows us to improve the estimates of alignment sizes for any given computational budget. We also discuss connections with rank-1 crowdsourcing models. Joint work with Tavor Baharav, David Tse (both from Stanford), and Ilan Shomorony (UIUC). Partly based on this manuscript: [Link] Bio: Govinda M Kamath is a post-doctoral researcher at Microsoft Research New England Research and Development center (MSR NERD), Cambridge, Massachusetts. He graduated with a PhD degree in Electrical Engineering from Stanford, and an ME from Indian Institute of Science. He works at the intersection of theory, algorithms, and statistics, with a particular interest in problems from computational genomics. A recurring theme he's fascinated with is that one can get significant computational savings in algorithmic problems by simply recasting the deterministic problem as an estimation problem.

Title: Spectral Algorithms and Multiarmed-Bandits in Pairwise Sequence Alignment

Speaker: Dr. Govinda Kamath, Microsoft Research, Cambridge

Abstract: Pairwise sequence alignment is often a computational bottleneck in genomic analysis pipelines, particularly in the context of third-generation sequencing technologies. To speed up this process, k-mer Jaccard similarities are often used as a proxy for alignment size to filter pairs of reads, and min-hashes are employed to efficiently estimate these similarities. However, when the k-mer distribution of a dataset is significantly non-uniform (e.g., due to GC biases or repeats), Jaccard similarity is no longer a good proxy for alignment size. We introduce a min-hash-based approach to estimate alignment sizes called Spectral Jaccard Similarity, which naturally accounts for uneven k-mer distributions. The Spectral Jaccard Similarity is computed by performing a singular value decomposition on a min-hash collision matrix. We show that this metric provides significantly better estimates for alignment sizes.We then explore the use of adaptivity to further speed up the estimation procedure. This involves using a multi-armed bandit algorithm to adaptively refine the alignment score estimates only for read pairs that are likely to have significant alignments. The resulting algorithm repeatedly performs a spectral decomposition of adaptively chosen submatrices. We show that adaptivity allows us to improve the estimates of alignment sizes for any given computational budget. We also discuss connections with rank-1 crowdsourcing models.
Joint work with Tavor Baharav, David Tse (both from Stanford), and Ilan Shomorony (UIUC). Partly based on this manuscript: [Link]

Bio: Govinda M Kamath is a post-doctoral researcher at Microsoft Research New England Research and Development center (MSR NERD), Cambridge, Massachusetts. He graduated with a PhD degree in Electrical Engineering from Stanford, and an ME from Indian Institute of Science. He works at the intersection of theory, algorithms, and statistics, with a particular interest in problems from computational genomics. A recurring theme he's fascinated with is that one can get significant computational savings in algorithmic problems by simply recasting the deterministic problem as an estimation problem.

Title: Is Caching the Missing Link in Wireless Communications?
Speaker: Prof. Petros Elia, EURECOM, France
Abstract: The talk will elaborate on the recent breakthroughs and open challenges in applying coded caching in wireless settings. We will see how the wireless medium forces a new set of fundamental challenges and bottlenecks which can -- unless dealt with -- all but dissolve some of the theoretical gains of coded caching as we know it. At the same time though, we will analyze some new opportunities that the wireless medium offers towards further leveraging the ideas behind coded multicasting. Some of these same ideas will also be extended in the wireless distributed computing scenarios, which we will discuss briefly. We will also elaborate on open challenges in deriving new information theoretic converse techniques, open challenges in applying combinatorics to reduce the subpacketization problem, as well as a variety of challenges for the communication theorists and network theorists in the audience. At the end, we will seek to shed light on a much more open-ended question: Can caching truly make a difference as a core technology in wireless communications? Bio: Petros Elia received the B.Sc. degree from the Illinois Institute of Technology, and the M.Sc. and Ph.D. degrees in electrical engineering from the University of Southern California (USC), Los Angeles, in 2001 and 2006 respectively. He is now a Professor with the Department of Communication Systems at EURECOM in Sophia Antipolis, France. His latest research deals with the intersection of coded caching and feedback-aided communications in multiuser settings. He has also worked in the area of complexity-constrained communications, MIMO, queueing theory and cross-layer design, coding theory, information theoretic limits in cooperative communications, and surveillance networks. He is a Fulbright scholar, the co-recipient of the NEWCOM++ distinguished achievement award 2008-2011 for a sequence of publications on the topic of complexity in wireless communications, and the recipient of the ERC Consolidator Grant 2017-2022 on cache-aided wireless communications.

Title: Is Caching the Missing Link in Wireless Communications?

Speaker: Prof. Petros Elia, EURECOM, France

Abstract: The talk will elaborate on the recent breakthroughs and open challenges in applying coded caching in wireless settings. We will see how the wireless medium forces a new set of fundamental challenges and bottlenecks which can -- unless dealt with -- all but dissolve some of the theoretical gains of coded caching as we know it. At the same time though, we will analyze some new opportunities that the wireless medium offers towards further leveraging the ideas behind coded multicasting. Some of these same ideas will also be extended in the wireless distributed computing scenarios, which we will discuss briefly. We will also elaborate on open challenges in deriving new information theoretic converse techniques, open challenges in applying combinatorics to reduce the subpacketization problem, as well as a variety of challenges for the communication theorists and network theorists in the audience. At the end, we will seek to shed light on a much more open-ended question: Can caching truly make a difference as a core technology in wireless communications?

Bio: Petros Elia received the B.Sc. degree from the Illinois Institute of Technology, and the M.Sc. and Ph.D. degrees in electrical engineering from the University of Southern California (USC), Los Angeles, in 2001 and 2006 respectively. He is now a Professor with the Department of Communication Systems at EURECOM in Sophia Antipolis, France. His latest research deals with the intersection of coded caching and feedback-aided communications in multiuser settings. He has also worked in the area of complexity-constrained communications, MIMO, queueing theory and cross-layer design, coding theory, information theoretic limits in cooperative communications, and surveillance networks. He is a Fulbright scholar, the co-recipient of the NEWCOM++ distinguished achievement award 2008-2011 for a sequence of publications on the topic of complexity in wireless communications, and the recipient of the ERC Consolidator Grant 2017-2022 on cache-aided wireless communications.

Title: Content Distribution with Coded Caching - Applications, System Design, and Implementation Challenges
Speaker: Andreas Dotzler, Cadami, Germany
Abstract: To be announced. Bio: Andreas Dotzler received a B.Sc. and Diploma in Information Technology at the Technische Universität Munich (TUM) in 2006 and 2008, respectively. During 2008-2015 he worked as a research assistant at the Associate Institute of Signal Processing (Prof. Utschick). His research interests include interference management in wireless networks, robust optimization of multi-antenna transmission strategies, and enhanced interference coordination for LTE-A. He is an inventor and co-inventor of several patents that emerged from a project with a major mobile service provider. In 2015 Andreas co-founded Cadami, a Munich (Germany) based company that provides solutions for wireless video streaming. Cadami is creating, promoting, and licensing intellectual property rights and software solutions that help to reduce network overload and increase video quality in high-traffic areas.

Title: Content Distribution with Coded Caching - Applications, System Design, and Implementation Challenges

Speaker: Andreas Dotzler, Cadami, Germany

Abstract: To be announced.

Bio: Andreas Dotzler received a B.Sc. and Diploma in Information Technology at the Technische Universität Munich (TUM) in 2006 and 2008, respectively. During 2008-2015 he worked as a research assistant at the Associate Institute of Signal Processing (Prof. Utschick). His research interests include interference management in wireless networks, robust optimization of multi-antenna transmission strategies, and enhanced interference coordination for LTE-A. He is an inventor and co-inventor of several patents that emerged from a project with a major mobile service provider. In 2015 Andreas co-founded Cadami, a Munich (Germany) based company that provides solutions for wireless video streaming. Cadami is creating, promoting, and licensing intellectual property rights and software solutions that help to reduce network overload and increase video quality in high-traffic areas.

Title: Balancing à la Knuth for DNA-based Data Storage
Speaker: Dr Han Mao Kiah, Nanyang Technological University, Singapore
Abstract: The imbalance of a binary word refers to the absolute difference between the number of ones and the number of zeros in it. A word is balanced if its imbalance is at most one and a code is balanced if all its codewords are balanced. In 1986, motivated by applications in optical disks, Knuth [1] proposed a simple and efficient scheme that transforms binary messages into balanced codes. In recent years, advances in synthesis and sequencing technologies have made DNA macromolecules an attractive medium for digital information storage. Besides being biochemically robust, DNA strands offer ultrahigh storage densities of 10^15 - 10^20 bytes per gram of DNA, as demonstrated in recent experiments (see [2, Table 1]). However, this non-traditional media presents new challenges to the coding community (see [3] for a survey). One particular challenge has rekindled interest in balanced codes. Specifically, a DNA string comprises four bases or letters: A, C, T and G, and a string is GC-rich (or GC-poor) if a high (or low) proportion of the bases corresponds to either G or C. Since GC-rich or GC-poor DNA strings are prone to both synthesis and sequencing errors, we aim to reduce the difference with the number of G and C and the number of A and T on every DNA codeword. This requirement is equivalent to reducing the imbalance of a related binary word. In this talk, we revisit Knuth's balancing method and look at techniques that adapt the method to address coding problems in DNA-based data storage. In the first part, we look at constructions of address sequences that are critical in DNA-based data storage with random-access capabilities. Specifically, Yazdi et al. [2] developed an architecture that allows selective access to encoded DNA strands through the process of hybridization. The technique involves prepending information-carrying DNA strands with specially chosen address sequences called primers. By combining Knuth's balancing method with cyclic codes, we provide efficient and explicit constructions of such primer sets [4]. In the second part, in addition to the GC-balanced constraints, we look at codes that correct a single insertion or deletion or substitution and whose codewords obey the homopolymer runlength constraints. Besides the code constructions, we also propose linear-time encoders for our codebooks [5]. In the third part, we apply Knuth's balancing method to a beautiful and important class of codes, the polar codes. Invented by Arıkan [6], polar codes achieve capacity for many channels with low encoding and decoding complexities. We study a generalization of Knuth's balancing method, specifically, a technique of Mazumdar, Roth, and Vontobel [7], and provide means of transforming messages into balanced polar codewords while retaining the low complexities of the polar encoding and decoding algorithms. References: [1] D. Knuth, "Efficient balanced codes," IEEE Transactions on Information Theory, vol. 32, no. 1, pp. 51–53, 1986. [2] S. H. T. Yazdi, R. Gabrys, and O. Milenkovic, "Portable and error-free DNA-based data storage," Scientific reports, vol. 7, no. 1, p. 5011, 2017. [3] S. Yazdi, H. M. Kiah, E. R. Garcia, J. Ma, H. Zhao, and O. Milenkovic, "DNA-based storage: Trends and methods," IEEE Trans. Molecular, Biological, Multi-Scale Communications, vol. 1, no. 3, pp. 230–248, 2015. [4] Y. M. Chee, H. M. Kiah, and H. Wei, "Efficient and explicit balanced primer codes," IEEE Transactions on Information Theory, vol. 66, no. 9, pp. 5344--5357, doi:10.1109/TIT.2020.2977915, 2020. [5] K. Cai, Y. M. Chee, R. Gabrys, H. M. Kiah, T. T. Nguyen, "Optimal Codes Correcting a Single Indel / Edit for DNA-Based Data Storage", preprint arXiv:1910.06501 (see also doi:10.1109/ISIT.2019.8849643, doi:10.1109/ICASSP40776.2020.9053256), 2019. [6] E. Arıkan. "Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels", IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, 2009. [7] A. Mazumdar, R. M. Roth, and P. O. Vontobel, "On linear balancing sets," Advances in Mathematics of Communications, vol. 4, no. 3,pp. 345–361, 2010. [8] U. Gupta, H. M. Kiah, A. Vardy, H. Yao, “Polar Codes with Balanced Codewords,” in 2020 IEEE International Symposium on Information Theory (ISIT), doi:10.1109/ISIT44484.2020.9174042, 2020. Bio: Han Mao Kiah received his Ph.D. degree in mathematics from Nanyang Technological University (NTU), Singapore, in 2014. From 2014 to 2015, he was a Postdoctoral Research Associate at the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign. From 2015 to 2018, he was a Lecturer at the School of Physical and Mathematical Sciences (SPMS), NTU, Singapore. Currently he is an Assistant Professor at SPMS, NTU, Singapore. His research interests include DNA-based data storage, coding theory, enumerative combinatorics and combinatorial design theory.

Title: Balancing à la Knuth for DNA-based Data Storage

Speaker: Dr Han Mao Kiah, Nanyang Technological University, Singapore

Abstract: The imbalance of a binary word refers to the absolute difference between the number of ones and the number of zeros in it. A word is balanced if its imbalance is at most one and a code is balanced if all its codewords are balanced. In 1986, motivated by applications in optical disks, Knuth [1] proposed a simple and efficient scheme that transforms binary messages into balanced codes. In recent years, advances in synthesis and sequencing technologies have made DNA macromolecules an attractive medium for digital information storage. Besides being biochemically robust, DNA strands offer ultrahigh storage densities of 10^15 - 10^20 bytes per gram of DNA, as demonstrated in recent experiments (see [2, Table 1]). However, this non-traditional media presents new challenges to the coding community (see [3] for a survey). One particular challenge has rekindled interest in balanced codes. Specifically, a DNA string comprises four bases or letters: A, C, T and G, and a string is GC-rich (or GC-poor) if a high (or low) proportion of the bases corresponds to either G or C. Since GC-rich or GC-poor DNA strings are prone to both synthesis and sequencing errors, we aim to reduce the difference with the number of G and C and the number of A and T on every DNA codeword. This requirement is equivalent to reducing the imbalance of a related binary word. In this talk, we revisit Knuth's balancing method and look at techniques that adapt the method to address coding problems in DNA-based data storage.

In the first part, we look at constructions of address sequences that are critical in DNA-based data storage with random-access capabilities. Specifically, Yazdi et al. [2] developed an architecture that allows selective access to encoded DNA strands through the process of hybridization. The technique involves prepending information-carrying DNA strands with specially chosen address sequences called primers. By combining Knuth's balancing method with cyclic codes, we provide efficient and explicit constructions of such primer sets [4].

In the second part, in addition to the GC-balanced constraints, we look at codes that correct a single insertion or deletion or substitution and whose codewords obey the homopolymer runlength constraints. Besides the code constructions, we also propose linear-time encoders for our codebooks [5].

In the third part, we apply Knuth's balancing method to a beautiful and important class of codes, the polar codes. Invented by Arıkan [6], polar codes achieve capacity for many channels with low encoding and decoding complexities. We study a generalization of Knuth's balancing method, specifically, a technique of Mazumdar, Roth, and Vontobel [7], and provide means of transforming messages into balanced polar codewords while retaining the low complexities of the polar encoding and decoding algorithms.

References: [1] D. Knuth, "Efficient balanced codes," IEEE Transactions on Information Theory, vol. 32, no. 1, pp. 51–53, 1986.
[2] S. H. T. Yazdi, R. Gabrys, and O. Milenkovic, "Portable and error-free DNA-based data storage," Scientific reports, vol. 7, no. 1, p. 5011, 2017.
[3] S. Yazdi, H. M. Kiah, E. R. Garcia, J. Ma, H. Zhao, and O. Milenkovic, "DNA-based storage: Trends and methods," IEEE Trans. Molecular, Biological, Multi-Scale Communications, vol. 1, no. 3, pp. 230–248, 2015.
[4] Y. M. Chee, H. M. Kiah, and H. Wei, "Efficient and explicit balanced primer codes," IEEE Transactions on Information Theory, vol. 66, no. 9, pp. 5344--5357, doi:10.1109/TIT.2020.2977915, 2020.
[5] K. Cai, Y. M. Chee, R. Gabrys, H. M. Kiah, T. T. Nguyen, "Optimal Codes Correcting a Single Indel / Edit for DNA-Based Data Storage", preprint arXiv:1910.06501 (see also doi:10.1109/ISIT.2019.8849643, doi:10.1109/ICASSP40776.2020.9053256), 2019.
[6] E. Arıkan. "Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels", IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, 2009.
[7] A. Mazumdar, R. M. Roth, and P. O. Vontobel, "On linear balancing sets," Advances in Mathematics of Communications, vol. 4, no. 3,pp. 345–361, 2010.
[8] U. Gupta, H. M. Kiah, A. Vardy, H. Yao, “Polar Codes with Balanced Codewords,” in 2020 IEEE International Symposium on Information Theory (ISIT), doi:10.1109/ISIT44484.2020.9174042, 2020.

Bio: Han Mao Kiah received his Ph.D. degree in mathematics from Nanyang Technological University (NTU), Singapore, in 2014. From 2014 to 2015, he was a Postdoctoral Research Associate at the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign. From 2015 to 2018, he was a Lecturer at the School of Physical and Mathematical Sciences (SPMS), NTU, Singapore. Currently he is an Assistant Professor at SPMS, NTU, Singapore. His research interests include DNA-based data storage, coding theory, enumerative combinatorics and combinatorial design theory.

Title: Communication in the Presence of Adversarial Jamming: The Curious Case of the Erasure Channel
Speaker: Prof. Sidharth Jaggi, University of Bristol and The Chinese University of Hong Kong
Abstract: Alice wishes to communicate with Bob, but the malicious jammer James wishes to stop this communication from occurring. What can she do? In this talk I'll explore recent discoveries/capacity-characterizations in a variety of settings (the role of causality in James' jamming, the role of myopicity in his observations, the interplay between these two, and the effect of rate-limited feedback). I'll focus on one of the simplest non-trivial jamming channels -- the case of a binary input channel, in which James may erase a constant fraction of transmissions -- even here, interesting phenomena occur. Time permitting, I may also briefly describe generalizations to other jamming channels/scenarios. Bio: B.Tech. ('00), EE, IIT Bombay, MS/Ph.D. ('05) EE, CalTech, Postdoctoral Associate ('06) LIDS, MIT. Currently Associate Professor in both the Dept. of Information Engineering at The Chinese University of Hong Kong, and the School of Mathematics at the University of Bristol. Research interests: Network coding and network error-correcting algorithms, coding theory, covert communication, sparse recovery.

Title: Communication in the Presence of Adversarial Jamming: The Curious Case of the Erasure Channel

Speaker: Prof. Sidharth Jaggi, University of Bristol and The Chinese University of Hong Kong

Abstract: Alice wishes to communicate with Bob, but the malicious jammer James wishes to stop this communication from occurring. What can she do? In this talk I'll explore recent discoveries/capacity-characterizations in a variety of settings (the role of causality in James' jamming, the role of myopicity in his observations, the interplay between these two, and the effect of rate-limited feedback). I'll focus on one of the simplest non-trivial jamming channels -- the case of a binary input channel, in which James may erase a constant fraction of transmissions -- even here, interesting phenomena occur. Time permitting, I may also briefly describe generalizations to other jamming channels/scenarios.

Bio: B.Tech. ('00), EE, IIT Bombay, MS/Ph.D. ('05) EE, CalTech, Postdoctoral Associate ('06) LIDS, MIT. Currently Associate Professor in both the Dept. of Information Engineering at The Chinese University of Hong Kong, and the School of Mathematics at the University of Bristol. Research interests: Network coding and network error-correcting algorithms, coding theory, covert communication, sparse recovery.

Title: Evolution of Modulation and Coding for Current Wireless Systems
Speaker: Dr. Sandip Sarkar, Sesovera, US
Abstract: The talk will focus on the evolution of modulation and coding to suit the needs of wireless communications. It will start off with the mechanism to support circuit switched voice over wireless networks, and then its evolution to support packet switched data. As data became the dominant traffic, MIMO started finding use. The arrival of 5G and its various use cases have made latency a premium as well. We will talk how LDPC and polar codes with distributed CRC helps achieve this goal, along with the use of higher order modulations, and dual codeword MIMO. Bio: Sandip Sarkar graduated from the Indian Institute of Technology in Kanpur, India with a bachelor’s degree in technology. He earned his Ph.D. in Electrical Engineering from Princeton University, and is currently the CTO of Sesovera, an Edge Based Artificial Intelligence and Machine Learning platform company, having pioneered the award winning HearZ platform - giving a voice interface to all gadgets and products. Before that Sandip was a Sr Director at Qualcomm the worldwide lead for 5G/LTE and the technical lead for the Qualcomm Engineering Simulation Tool (QUEST™), a robust tool that analyzes live network data, helping operators more precisely track network performance and identify bottlenecks. Sarkar was initially hired by Qualcomm as a senior engineer and worked on Globalstar modem design and Condor encryption algorithm design. Later, he became the cdma2000 reverse link systems lead, and subsequently served as the editor for the cdma2000 physical layer and band class specifications. Then, he served as the MIMO lead for 3GPP, the UMB and LTE standards delegate for Qualcomm, and the editor for UMB physical layer specifications as well. Dedicated to the highest degree of EE professionalism, Sarkar is a member of ComSoc. He has served as a chairman of the physical layer text group as well as an editor for 3GPP2 specifications. Sarkar was elected as a senior member of IEEE in 2003. He holds more that 300+ worldwide patents. He has authored and published more than 30 technical papers in various IEEE and other technical journals and his name has appeared in “Marquis Who’s Who in America” since 2006.

Title: Evolution of Modulation and Coding for Current Wireless Systems

Speaker: Dr. Sandip Sarkar, Sesovera, US

Abstract: The talk will focus on the evolution of modulation and coding to suit the needs of wireless communications. It will start off with the mechanism to support circuit switched voice over wireless networks, and then its evolution to support packet switched data. As data became the dominant traffic, MIMO started finding use. The arrival of 5G and its various use cases have made latency a premium as well. We will talk how LDPC and polar codes with distributed CRC helps achieve this goal, along with the use of higher order modulations, and dual codeword MIMO.

Bio: Sandip Sarkar graduated from the Indian Institute of Technology in Kanpur, India with a bachelor’s degree in technology. He earned his Ph.D. in Electrical Engineering from Princeton University, and is currently the CTO of Sesovera, an Edge Based Artificial Intelligence and Machine Learning platform company, having pioneered the award winning HearZ platform - giving a voice interface to all gadgets and products. Before that Sandip was a Sr Director at Qualcomm the worldwide lead for 5G/LTE and the technical lead for the Qualcomm Engineering Simulation Tool (QUEST™), a robust tool that analyzes live network data, helping operators more precisely track network performance and identify bottlenecks.
Sarkar was initially hired by Qualcomm as a senior engineer and worked on Globalstar modem design and Condor encryption algorithm design. Later, he became the cdma2000 reverse link systems lead, and subsequently served as the editor for the cdma2000 physical layer and band class specifications. Then, he served as the MIMO lead for 3GPP, the UMB and LTE standards delegate for Qualcomm, and the editor for UMB physical layer specifications as well. Dedicated to the highest degree of EE professionalism, Sarkar is a member of ComSoc. He has served as a chairman of the physical layer text group as well as an editor for 3GPP2 specifications. Sarkar was elected as a senior member of IEEE in 2003. He holds more that 300+ worldwide patents. He has authored and published more than 30 technical papers in various IEEE and other technical journals and his name has appeared in “Marquis Who’s Who in America” since 2006.

Title: Sampling from Probability Distributions on Lattices
Speaker: Prof. Navin Kashyap, IISc Bangalore
Abstract: Let L be a full-dimensional lattice in R^d, and let B be a generator matrix for L. In other words, B is an d x d full-rank matrix such that L consists of all the points Bz, as z ranges over the integer lattice Z^d. Let f(x) be a probability density on R^d. We then define a probability distribution, P, on L as follows: for each lattice point k in L, P(k) = (1/A) f(k), where A = \sum_k f(k) is the normalization constant. Our aim is to devise efficient algorithms for generating independent samples from the distribution P. Instances of this problem arise in various contexts in MIMO wireless communications, information and coding theory, cryptography, and information-theoretic security. Sampling from the lattice Gaussian distribution, i.e., when f(x) is a Gaussian density, is particularly well-studied. In this talk, we describe some general Markov Chain Monte Carlo (MCMC) sampling schemes that work for any given density f. At the heart of our approach is the use of Hamiltonian Monte Carlo (HMC) to generate samples from the density f. For one of our HMC-based schemes, simulation results indicate far superior performance over any existing sampling scheme for the lattice Gaussian. In particular, our scheme scales well with dimension d. The talk is based on joint work with my students Anand Jerry George and Anaswara S. Bio: Navin Kashyap received a B.Tech. degree in Electrical Engineering from the Indian Institute of Technology, Bombay, in 1995, an M.S. in Electrical Engineering from the University of Missouri-Rolla in 1997, and an M.S. in Mathematics and a Ph.D. in Electrical Engineering: Systems from the University of Michigan, Ann Arbor, in 2001. After a two-year postdoctoral stint at the University of California, San Diego, he joined the faculty of the Department of Mathematics and Statistics at Queen's University, Kingston, Ontario, Canada, where he remained till December 2010. Thereafter, he has been with the Department of Electrical Communication Engineering at the Indian Institute of Science, where he is currently a Professor. His research interests lie primarily in the application of combinatorial and probabilistic methods in information and coding theory. Prof. Kashyap served on the editorial board of the IEEE Transactions on Information Theory during the period 2009-2014. He was appointed as a Distinguished Lecturer of the Information Theory Society for 2017-2018. He is a recipient of the Swarnajayanti Fellowship awarded by the Department of Science and Technology. He is at present an Associate Editor for the SIAM Journal on Discrete Mathematics, and the Springer journal Cryptography and Communications.

Title: Sampling from Probability Distributions on Lattices

Speaker: Prof. Navin Kashyap, IISc Bangalore

Abstract: Let L be a full-dimensional lattice in R^d, and let B be a generator matrix for L. In other words, B is an d x d full-rank matrix such that L consists of all the points Bz, as z ranges over the integer lattice Z^d. Let f(x) be a probability density on R^d. We then define a probability distribution, P, on L as follows: for each lattice point k in L, P(k) = (1/A) f(k), where A = \sum_k f(k) is the normalization constant. Our aim is to devise efficient algorithms for generating independent samples from the distribution P. Instances of this problem arise in various contexts in MIMO wireless communications, information and coding theory, cryptography, and information-theoretic security. Sampling from the lattice Gaussian distribution, i.e., when f(x) is a Gaussian density, is particularly well-studied. In this talk, we describe some general Markov Chain Monte Carlo (MCMC) sampling schemes that work for any given density f. At the heart of our approach is the use of Hamiltonian Monte Carlo (HMC) to generate samples from the density f. For one of our HMC-based schemes, simulation results indicate far superior performance over any existing sampling scheme for the lattice Gaussian. In particular, our scheme scales well with dimension d. The talk is based on joint work with my students Anand Jerry George and Anaswara S.

Bio: Navin Kashyap received a B.Tech. degree in Electrical Engineering from the Indian Institute of Technology, Bombay, in 1995, an M.S. in Electrical Engineering from the University of Missouri-Rolla in 1997, and an M.S. in Mathematics and a Ph.D. in Electrical Engineering: Systems from the University of Michigan, Ann Arbor, in 2001. After a two-year postdoctoral stint at the University of California, San Diego, he joined the faculty of the Department of Mathematics and Statistics at Queen's University, Kingston, Ontario, Canada, where he remained till December 2010. Thereafter, he has been with the Department of Electrical Communication Engineering at the Indian Institute of Science, where he is currently a Professor. His research interests lie primarily in the application of combinatorial and probabilistic methods in information and coding theory. Prof. Kashyap served on the editorial board of the IEEE Transactions on Information Theory during the period 2009-2014. He was appointed as a Distinguished Lecturer of the Information Theory Society for 2017-2018. He is a recipient of the Swarnajayanti Fellowship awarded by the Department of Science and Technology. He is at present an Associate Editor for the SIAM Journal on Discrete Mathematics, and the Springer journal Cryptography and Communications.

Title: Practical Strategies for Synthesizing Shared Secret Keys at the Physical Layer in Wireless Networks
Speaker: Dr. Harshan Jagadeesh, IIT Delhi
Abstract: Given the broadcast nature of wireless communication, it is well known that messages transmitted to an intended receiver can also be heard by eavesdroppers in the vicinity. A standard technique to circumvent this problem is to employ crypto-primitives at the higher-layer of the protocol stack. With symmetric-key encryption techniques favored for applications involving resource-constrained wireless devices, the communicating parties need to acquire a pre-shared secret-key to execute the crypto-primitives. While a plethora of crypto-techniques are well known for key-exchange mechanisms, the idea of physical-layer key generation has also received traction wherein the wireless nodes extract secret keys using the common randomness offered by the channel realizations. In the first part of the presentation, an overview on the topic of physical-layer secret-key generation will be presented by covering the underlying ideas and some recent developments in the field. Subsequently, the presentation will address a specific problem of synthesizing group secret-keys, wherein two or more wireless nodes in a network harvest secret-keys for broadcast and relaying applications. In this part, several questions on the performance of key generation methods will be discussed, primarily: (i) how to design practical strategies for sharing the common randomness, (ii) how to ensure confidentiality when sharing the common randomness, (iii) how to design quantization algorithms to generate high-rate secret-keys with maximum entropy, and (iv) how to design reconciliation algorithms to minimize the mismatch-rate among the nodes. Bio: J. Harshan is an Assistant Professor in the Department of Electrical Engineering, Indian Institute of Technology Delhi. He obtained his Ph.D. from the Department of Electrical Communication Engineering, Indian Institute of Science, India. Prior to joining IIT Delhi, he was with the CyberSecurity group at Advanced Digital Sciences Center, Singapore. Before that he held postdoctoral positions at the Division of Mathematical Sciences, Nanyang Technological University, Singapore and at the Department of Electrical and Computer Systems Engineering at Monash University, Australia. His research interests include security, wireless networks, and applications of information and coding theory to communications and storage.

Title: Practical Strategies for Synthesizing Shared Secret Keys at the Physical Layer in Wireless Networks

Speaker: Dr. Harshan Jagadeesh, IIT Delhi

Abstract: Given the broadcast nature of wireless communication, it is well known that messages transmitted to an intended receiver can also be heard by eavesdroppers in the vicinity. A standard technique to circumvent this problem is to employ crypto-primitives at the higher-layer of the protocol stack. With symmetric-key encryption techniques favored for applications involving resource-constrained wireless devices, the communicating parties need to acquire a pre-shared secret-key to execute the crypto-primitives. While a plethora of crypto-techniques are well known for key-exchange mechanisms, the idea of physical-layer key generation has also received traction wherein the wireless nodes extract secret keys using the common randomness offered by the channel realizations. In the first part of the presentation, an overview on the topic of physical-layer secret-key generation will be presented by covering the underlying ideas and some recent developments in the field. Subsequently, the presentation will address a specific problem of synthesizing group secret-keys, wherein two or more wireless nodes in a network harvest secret-keys for broadcast and relaying applications. In this part, several questions on the performance of key generation methods will be discussed, primarily: (i) how to design practical strategies for sharing the common randomness, (ii) how to ensure confidentiality when sharing the common randomness, (iii) how to design quantization algorithms to generate high-rate secret-keys with maximum entropy, and (iv) how to design reconciliation algorithms to minimize the mismatch-rate among the nodes.

Bio: J. Harshan is an Assistant Professor in the Department of Electrical Engineering, Indian Institute of Technology Delhi. He obtained his Ph.D. from the Department of Electrical Communication Engineering, Indian Institute of Science, India. Prior to joining IIT Delhi, he was with the CyberSecurity group at Advanced Digital Sciences Center, Singapore. Before that he held postdoctoral positions at the Division of Mathematical Sciences, Nanyang Technological University, Singapore and at the Department of Electrical and Computer Systems Engineering at Monash University, Australia. His research interests include security, wireless networks, and applications of information and coding theory to communications and storage.

Title: On the Problem of Repairing Reed-Solomon Codes
Speaker: Dr. Son Hoang Dau, RMIT University, Australia
Abstract: Reed-Solomon (RS) codes are employed in most major distributed storage systems, e.g. Google File Systems II, Hadoop Distributed File System, Quantcast File Systems, Facebook's f4, Yahoo's Object Store, Baidu Atlas Cloud Storage, and Backblaze Vaults, providing these systems with data redundancy, fault tolerance, and availability. Despite their several advantages such as storage overhead optimality and parameter flexibility, in their default repair scheme, RS codes incur prohibitively high repair bandwidths, which makes the recovery process very costly. For instance, it has been observed that the bandwidth used for repairing RS-coded data in a Facebook analytics cluster amounts to 10%-20% of the total network traffic within the cluster. Here, the repair bandwidth is defined to be the amount of data a replacement node must download from the other storage nodes when recovering the content of a failed node. In this talk we will discuss different approaches to the problem of repairing RS codes efficiently, from both a theoretical and practical points of view. We will also present some latest results we obtained recently and some on-going work on repairing the RS codes currently employed by the industry. Bio: Hoang Dau received the B.S. degree in applied mathematics and informatics from Vietnam National University, Hanoi, Vietnam, in 2006, and the M.S. and Ph.D. degrees in mathematics from Nanyang Technological University, Singapore, in 2009 and 2012, respectively. He is now a lecturer at the Discipline of Computer Science & Information Technology, School of Science, RMIT University, Australia. His research interests include coding theory, combinatorics, and blockchains. He currently leads a 3-year project on advanced coding techniques for fast failure recovery in storage systems, awarded by the Australian Research Council (2018-2021).

Title: On the Problem of Repairing Reed-Solomon Codes

Speaker: Dr. Son Hoang Dau, RMIT University, Australia

Abstract: Reed-Solomon (RS) codes are employed in most major distributed storage systems, e.g. Google File Systems II, Hadoop Distributed File System, Quantcast File Systems, Facebook's f4, Yahoo's Object Store, Baidu Atlas Cloud Storage, and Backblaze Vaults, providing these systems with data redundancy, fault tolerance, and availability. Despite their several advantages such as storage overhead optimality and parameter flexibility, in their default repair scheme, RS codes incur prohibitively high repair bandwidths, which makes the recovery process very costly. For instance, it has been observed that the bandwidth used for repairing RS-coded data in a Facebook analytics cluster amounts to 10%-20% of the total network traffic within the cluster. Here, the repair bandwidth is defined to be the amount of data a replacement node must download from the other storage nodes when recovering the content of a failed node.

In this talk we will discuss different approaches to the problem of repairing RS codes efficiently, from both a theoretical and practical points of view. We will also present some latest results we obtained recently and some on-going work on repairing the RS codes currently employed by the industry.

Bio: Hoang Dau received the B.S. degree in applied mathematics and informatics from Vietnam National University, Hanoi, Vietnam, in 2006, and the M.S. and Ph.D. degrees in mathematics from Nanyang Technological University, Singapore, in 2009 and 2012, respectively. He is now a lecturer at the Discipline of Computer Science & Information Technology, School of Science, RMIT University, Australia. His research interests include coding theory, combinatorics, and blockchains. He currently leads a 3-year project on advanced coding techniques for fast failure recovery in storage systems, awarded by the Australian Research Council (2018-2021).

2020 Hyderabad Workshop on Information Theory

September - October 2020

Details of the talks