More Like this

1. Optimal Learning Rate of Sending One Bit Over Arbitrary Acyclic BISO-Channel Networks

   https://doi.org/10.1109/ISIT54713.2023.10206476  

   Wang, Chih-Chun; Love, David J. (June 2023, IEEE)

   This work considers the problem of sending a 1-bit message over an acyclic network, where the “edge” connecting any two nodes is a memoryless binary-input/symmetric-output (BISO) channel. For any arbitrary acyclic network topology and constituent channel models, a min-cut-based converse of the learning rate, denoted by r^*, is derived. It is then shown that for any r < r^*, one can design a scheme with learning rate r. Capable of approaching the optimal r^*, the proposed scheme is thus the asymptotically fastest for sending one bit over any acyclic BISO-channel network. The construction is based on a new concept of Lossless Amplify-&-Forward, a sharp departure from existing multi-hop communication scheme designs. 

   more » « less
2. Accelerating Polarization via Alphabet Extension

   Duursma, Iwan; Gabrys, Ryan; Guruswami, Venkatesan; Lin, Ting-Chun; Wang, Hsin-Po (September 2022, Leibniz international proceedings in informatics)

   Polarization is an unprecedented coding technique in that it not only achieves channel capacity, but also does so at a faster speed of convergence than any other technique. This speed is measured by the "scaling exponent" and its importance is three-fold. Firstly, estimating the scaling exponent is challenging and demands a deeper understanding of the dynamics of communication channels. Secondly, scaling exponents serve as a benchmark for different variants of polar codes that helps us select the proper variant for real-life applications. Thirdly, the need to optimize for the scaling exponent sheds light on how to reinforce the design of polar code. In this paper, we generalize the binary erasure channel (BEC), the simplest communication channel and the protagonist of many polar code studies, to the "tetrahedral erasure channel" (TEC). We then invoke Mori-Tanaka’s 2 × 2 matrix over 𝔽_4 to construct polar codes over TEC. Our main contribution is showing that the dynamic of TECs converges to an almost-one-parameter family of channels, which then leads to an upper bound of 3.328 on the scaling exponent. This is the first non-binary matrix whose scaling exponent is upper-bounded. It also polarizes BEC faster than all known binary matrices up to 23 × 23 in size. Our result indicates that expanding the alphabet is a more effective and practical alternative to enlarging the matrix in order to achieve faster polarization. 

   more » « less
3. A Wringing-Based Proof of a Second-Order Converse for the Multiple-Access Channel under Maximal Error Probability

   https://doi.org/10.1109/ISIT45174.2021.9518136  

   Wei, Fei; Kosut, Oliver (July 2021, 2021 IEEE International Symposium on Information Theory (ISIT))

   null (Ed.)

   The second-order converse bound of multiple access channels is an intriguing problem in information theory. In this work, in the setting of the two-user discrete memoryless multiple access channel (DM-MAC) under the maximal error probability criterion, we investigate the gap between the best achievable rates and the asymptotic capacity region. With “wringing techniques” and meta-converse arguments, we show that gap at blocklength n is upper bounded by O(1/√n) . 

   more » « less
4. JVM fuzzing for JIT-induced side-channel detection

   https://doi.org/10.1145/3377811.3380432  

   Brennan, Tegan; Saha, Seemanta; Bultan, Tevfik (June 2020, ICSE '20: Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering)

   null (Ed.)

   Timing side channels arise in software when a program's execution time can be correlated with security-sensitive program input. Recent results on software side-channel detection focus on analysis of program's source code. However, runtime behavior, in particular optimizations introduced during just-in-time (JIT) compilation, can impact or even introduce timing side channels in programs. In this paper, we present a technique for automatically detecting such JIT-induced timing side channels in Java programs. We first introduce patterns to detect partitions of secret input potentially separable by side channels. Then we present an automated approach for exploring behaviors of the Java Virtual Machine (JVM) to identify states where timing channels separating these partitions arise. We evaluate our technique on three datasets used in recent work on side-channel detection. We find that many code variants labeled "safe" with respect to side-channel vulnerabilities are in fact vulnerable to JIT-induced timing side channels. Our results directly contradict the conclusions of four separate state-of-the-art program analysis tools for side-channel detection and demonstrate that JIT-induced side channels are prevalent and can be detected automatically. 

   more » « less
5. Channel coding at low capacity

   Fereydounian, Mohammad; Hassani, Hamed; Jamal, Vahid; Mahdavifar, Hessam (August 2023, IEEE journal on selected areas in information theory)

   Low-capacity scenarios have become increasingly important in the technology of the In- ternet of Things (IoT) and the next generation of wireless networks. Such scenarios require efficient and reliable transmission over channels with an extremely small capacity. Within these constraints, the state-of-the-art coding techniques may not be directly applicable. More- over, the prior work on the finite-length analysis of optimal channel coding provides inaccurate predictions of the limits in the low-capacity regime. In this paper, we study channel coding at low capacity from two perspectives: fundamental limits at finite length and code construc- tions. We first specify what a low-capacity regime means. We then characterize finite-length fundamental limits of channel coding in the low-capacity regime for various types of channels, including binary erasure channels (BECs), binary symmetric channels (BSCs), and additive white Gaussian noise (AWGN) channels. From the code construction perspective, we charac- terize the optimal number of repetitions for transmission over binary memoryless symmetric (BMS) channels, in terms of the code blocklength and the underlying channel capacity, such that the capacity loss due to the repetition is negligible. Furthermore, it is shown that capacity- achieving polar codes naturally adopt the aforementioned optimal number of repetitions. 

   more » « less