Title: Semiquantitative Group Testing with Applications
Olgica Milenkovic, University of Illinois at Urbana-Champaign
Semiquantitative group testing (SQGT) is a group testing scheme motivated by a class of problems arising in genome screening experiments and testing for infectious diseases. SQGT may be viewed as a concatenation of an adder channel and an integer-valued quantizer and it represents a unifying framework for group testing and quantized compressive sensing. We will review the notions of SQ-disjunct and SQ-separable codes, and describe several combinatorial and probabilistic constructions for such codes. While for most of these constructions we assume that the number of defectives is significantly smaller than the total number of test subjects, we also consider the case for which there is no restriction on the number of defectives. We also review efficient decoding algorithms and describe an important application of this testing method for real time reverse-transcriptase polymerase chain reaction used as a gold standard for Covid-19 screening.
Olgica Milenkovic is a professor of Electrical and Computer Engineering at the University of Illinois, Urbana-Champaign (UIUC), and Research Professor at the Coordinated Science Laboratory. She obtained her Masters Degree in Mathematics in 2001 and PhD in Electrical Engineering in 2002, both from the University of Michigan, Ann Arbor. Prof. Milenkovic heads a group focused on addressing unique interdisciplinary research challenges spanning the areas of algorithm design and computing, bioinformatics, coding theory, machine learning and signal processing. Her scholarly contributions have been recognized by multiple awards, including the NSF Faculty Early Career Development (CAREER) Award, the DARPA Young Faculty Award, the Dean's Excellence in Research Award, and several best paper awards. In 2013, she was elected a UIUC Center for Advanced Study Associate and Willett Scholar while in 2015 she was elected a Distinguished Lecturer of the Information Theory Society. In 2018 she became an IEEE Fellow. She has served as Associate Editor of the IEEE Transactions of Communications, the IEEE Transactions on Signal Processing, the IEEE Transactions on Information Theory and the IEEE Transactions on Molecular, Biological and Multi-Scale Communications. In 2009, she was the Guest Editor in Chief of a special issue of the IEEE Transactions on Information Theory on Molecular Biology and Neuroscience.
Title: Information-Theoretic Anonymous Cryptographic Protocols
Masahito Hayashi, Southern University of Science and Technology/Nagoya University
In this talk, we present two information-theoretic cryptographic tasks related to anonymity and their protocols. One is secure list decoding and the other is multi-party anonymous unanimous approval.
Secure list decoding is an extended task of list decoding by adding security requirements. While the conventional list decoding requires that the list contains the transmitted message, secure list decoding requires the following additional security conditions. The first additional security condition is the impossibility of the correct decoding, i.e., the receiver cannot uniquely identify the transmitted message even though the transmitted message is contained in the list. This condition can be trivially satisfied when the transmission rate is larger than the channel capacity. The other additional security condition is the impossibility for the sender to estimate another element of the decoded list except for the transmitted message. This protocol can be used for anonymous auction, which realizes the anonymity for bidding. We characterize the asymptotic achievable rate region for this task when these requirements are required information-theoretically.
Multi-party anonymous unanimous approval is a task when a certain project written as the variable $Y \in F_q^d$ requires the approvals from all of m players. Our requirements are the following. We verify that all m players approve the project by confirming the contents Y. Also, the correctness of distributed contents among the m players needed to be verified. When a player disagrees, the player cannot be identified. This task can be realized information-theoretically by using secure modulo summation, which is a new cryptographic resource.
A part of the presented results is a joint work with Takeshi Koshiba.
References: Proc. ISIT2019, pp. 1727 -- 1731; https://arxiv.org/abs/1901.02590; https://arxiv.org/abs/1910.05976; https://arxiv.org/abs/1812.10862; https://eprint.iacr.org/2018/802.pdf
Masahito Hayashi received the B.S. degree from the Faculty of Sciences in Kyoto University, Japan, in 1994 and the M.S. and Ph.D. degrees in Mathematics from Kyoto University, Japan, in 1996 and 1999, respectively. He worked in Kyoto University as a Research Fellow of the Japan Society of the Promotion of Science (JSPS) from 1998 to 2000, and worked in the Laboratory for Mathematical Neuroscience, Brain Science Institute, RIKEN from 2000 to 2003, and worked in ERATO Quantum Computation and Information Project, Japan Science and Technology Agency (JST) as the Research Head from 2000 to 2006. He worked in the Graduate School of Information Sciences, Tohoku University as Associate Professor from 2007 to 2012. In 2012, he joined the Graduate School of Mathematics, Nagoya University as Professor. In 2020, he joined Shenzhen Institute for Quantum Science and Engineering, Southern University of Science and Technology, Shenzhen, China as Chief Research Scientist. In 2011, he received Information Theory Society Paper Award (2011) for ``Information-Spectrum Approach to Second-Order Coding Rate in Channel Coding''. In 2016, he received the Japan Academy Medal from the Japan Academy and the JSPS Prize from Japan Society for the Promotion of Science. In 2017, he was promoted to IEEE Fellow.
In 2006, he published the book ``Quantum Information: An Introduction'' from Springer, whose revised version was published as ``Quantum Information Theory: Mathematical Foundation'' from Graduate Texts in Physics, Springer in 2016. In 2016, he published other two books ``Group Representation for Quantum Theory'' and ``A Group Theoretic Approach to Quantum Information'' from Springer. His research interests include classical and quantum information theory and classical and quantum statistical inference.
Title: Costly Constrained Channels: Theory and Applications
Paul H. Siegel, University of California; San Diego
Finite-state noiseless channels with symbol costs - or, costly constrained channels - trace their origins to Shannon’s analysis of the telegraph channel in 1948. They serve as useful models in many data transmission, storage, and networking scenarios. The study of their information-theoretic properties has fascinating intersections with analytical combinatorics, matrix analysis, optimization theory, and the theory of finite-state Markov chains. A variety of algorithmic approaches to designing efficient codes have been proposed, drawing on enumerative methods, source coding, symbolic dynamics, and tree coding
In this talk, I will present two recent problems in information storage that can be formulated in terms of costly constrained channels: rate-constrained data shaping to extend the lifetime of flash memory, and coding for efficient strand synthesis in DNA-based data storage. I will discuss theoretical results and coding schemes, both old and new, that have been used to address them, highlighting several of the interesting connections mentioned above.
Paul Siegel is a Distinguished Professor of Electrical and Computer Engineering in the Jacobs School of Engineering at the University of California San Diego, where he holds an endowed chair at the Center for Memory and Recording Research. He received undergraduate and graduate degrees in mathematics from the Massachusetts Institute of Technology in 1975 and 1979, respectively. He held a Chaim Weizmann Postdoctoral Fellowship with the Courant Institute at New York University. He was with the IBM Research Division in San Jose, California from 1980 to 1995, and joined the faculty at UC San Diego in 1995.
Prof. Siegel has been working on applications of information theory and coding to problems in data storage for 40 years. He was co-recipient of the 1992 IEEE Information Theory Society Paper Award and the 1993 IEEE Communications Society Leonard G. Abraham Prize Paper Award in recognition of his work in this area. He was also co-recipient of the 2007 Best Paper Award in Signal Processing and Coding for Data Storage from the Data Storage Technical Committee of the IEEE Communications Society. He was the Padovani Lecturer of the IEEE Information Theory Society in 2015. He is an IEEE Fellow and a member of the U.S. National Academy of Engineering.
Prof. Siegel was a Member of the Board of Governors of the IEEE Information Theory Society from 1991 to 1996 and from 2009 to 2014. He served the IEEE Transactions on Information Theory as Co-Guest Editor of the 1991 Special Issue on Coding for Storage Devices, Associate Editor of Coding Techniques from 1992 to 1995, and Editor-in-Chief from 2001 to 2004. He also served the IEEE Journal on Selected Areas in Communications as Co-Guest Editor of the 2001 two-part issue on The Turbo Principle: From Theory to Practice and the 2016 issue on Recent Advances in Capacity Approaching Codes.