Mohammad

Ali

Maddah-Ali

(Sharif University of Technology, Iran)
Plenary: Coding for Distributed Information Systems: Adversarial Sources and Approximated Decoding
Oct 18, 2021

Presenter(s):

Mohammad

Ali

Maddah-Ali

(Sharif University of Technology, Iran)
Abstract:
Coding is known as an effective approach to deal with some of the major challenges in distributed information systems in terms of security of the network, privacy of the data, and efficiency of the resource management. The current solutions are often based on expanding the existing coding tools and techniques, still following the conventional mindset. In this talk, we argue that there are some major scenarios and thread models that do not conform with the traditional rules. For example: (1) Coding techniques are often designed for "exact error-free decoding". However, in some scenarios, e.g. straggler-resistance computing for machine learning, only an "approximate decoding" is enough, (2) In conventional coding techniques, "input sources" are supposed to be conveyed and decoded correctly. However, in some scenarios (e.g. sharded blockchains), some parts of "input symbols" are chosen and distributed adversarially to prevent "other input symbols" from being recovered correctly. In this talk, we will review some solutions and bounds for those scenarios and discuss some open problems.

Plenary: Communication and Sensing: From Compressed Sampling to Model-based Deep Learning
Oct 19, 2021

Presenter(s):

Yonina

Eldar

(Weizmann Institute of Science, Israel)
Abstract:
The famous Shannon-Nyquist theorem has become a landmark in analog to digital conversion and the development of digital signal processing algorithms. However, in many modern applications, the signal bandwidths have increased tremendously, while the acquisition capabilities have not scaled sufficiently fast. Furthermore, the resulting high rate digital data requires storage, communication and processing at very high rates which is computationally expensive and requires large amounts of power. In this talk we consider a general framework for communication and sensing including sub-Nyquist sampling, quantization and processing in space, time and frequency which allows to dramatically reduce the number of antennas, sampling rates, number of bits and band occupancy in a variety of applications. Our framework relies on exploiting signal structure, quantization and the processing task in both standard processing and in deep learning networks leading to a new framework for model-based deep learning. It also allows for the development of efficient joint radar-communication systems. We consider applications of these ideas to a variety of problems in wireless communications, imaging, efficient massive MIMO systems, automotive radar and ultrasound imaging and show several demos of real-time sub-Nyquist prototypes including a wireless ultrasound probe, sub-Nyquist automotive radar, cognitive radio and radar, dual radar-communication systems, analog precoding, sparse antenna arrays, and a deep Viterbi decoder. We end by discussing more generally how models can be used in deep learning methods with application to a variety of communication settings.

Presenter(s):

Yasutada

Oohama

(University of Electro-Communications)
Abstract:
In this plenary talk we present our previous works on information theoretic security consisting of three miscellaneous topics. Those topics provide some specific but interesting problems arising inherently in communication systems with security requirement. The first topics is the relay channel with confidential messages (the RCC), which provides an interesting subject discussing an interplay between the two roles of the relay as a “helper” and as an “eavesdropper”. The second topics is the broadcast channel with confidential messages (the BCC) with randomness constraints stochastic encoders. In the BCC, we study a practical problem that we have some resource constraint on “dummy random variables” used for the stochastic encoders. The third topic is our recent work on an information theoretic analysis of the Shannon cipher system under side-channel attacks. In this topics we discuss some interesting relationship between the privacy amplification and the strong converse theorem for a certain multiterminal source coding system.

Plenary: Short Packets over Wireless Fading Networks
Oct 21, 2021

Presenter(s):

Giuseppe

Durisi

(Chalmers University of Technology, Sweden)
Abstract:
To support the Internet-of-Things vision of enabling distributed autonomous systems operating in real time, we need a new wireless infrastructure, able to provide highly reliable and low-latency connectivity to a large number of sporadically active devices transmitting short data packets. In this talk, I will illustrate how to use recent results from finite-blocklength information theory to optimally design such a wireless infrastructure. Scenarios that are relevant for 5G and beyond will be presented. In particular, I will discuss how to support low-latency, ultra-reliable communications in both cellular and cell-free massive multiple-input multiple-output architectures.

Tutorial: Code-Based Cryptography
Oct 17, 2021

Presenter(s):
,

Sven

Puchinger

(Technical University of Munich, Germany)
Antonia

Wachter-Zeh

(Technical University of Munich, Germany)
Abstract:
Currently-used public-key cryptosystems based on number-theoretic problems are threatened by the possibility that large-scale quantum computers will be built in the near future; Shor’s algorithm is able to solve these seemingly hard problems in polynomial time on such computers. In this context, the National Institute of Standards and Technology (NIST) has initiated a standardization process for public key encryption (PKE) schemes, key encapsulation mechanisms (KEM), and signatures. The standardization process has now reached Round 3, where lattice-based and code-based cryptography play a prominent role. These code-based cryptosystems include most prominently the classical McEliece system. Their security is based on hard computational problems in coding theory, and encryption and decryption often correspond to en- and decoding of an error-correcting code.
The goal of this tutorial is to provide an overview of important existing code-based cryptosystems, their security, and current challenges in the area of code-based cryptosystems. We will thereby consider amongst others systems based on Goppa, Moderate-Density-Parity-Check (MDPC), and rank-metric codes.

Presenter(s):
,

Peter

Trifonov

(ITMO University)
Grigorii

Trofimiuk

(ITMO University, Russia)
Abstract:
Polar codes with large kernels were recently shown to asymptotically achieve optimal scaling exponent. However, these codes were believed to be impractical due to lack of efficient decoding algorithms. In this tutorial we present a toolset for design and decoding of polar codes with large kernels. In particular, detailed treatment of recursive trellis and window kernel processing algorithms will be provided. These algorithms together with the successive cancellation list decoder allow one to obtain the same performance with lower complexity compared to polar codes with Arikan kernel. We present also techniques for construction of polar codes with large kernels, as well as kernels with good polarization properties and low decoding complexity.

Presenter(s):
,
,

Vaneet

Aggarwal

(Purdue University, USA)
Tian

Lan

(George Washington University, USA)
Parimal

Parag

(Indian Institute of Science, Bangalore, India)
Abstract:
As consumers are increasingly engaged in social networking and E-commerce activities, businesses grow to rely on Big Data analytics for intelligence, and traditional IT infrastructure continues to migrate to the cloud and edge, these trends cause distributed data storage demand to rise at an unprecedented speed. Erasure coding has seen itself quickly emerged as a promising technique to reduce storage cost while providing similar reliability as replicated systems, widely adopted by companies like Facebook, Microsoft and Google. However, it also brings new challenges in characterizing and optimizing the access latency when erasure codes are used in distributed storage. The aim of this tutorial is to provide a review of recent progress (both theoretical and practical) on systems that employ erasure codes for distributed storage.
In this tutorial, we will first identify the key challenges and taxonomy of the research problems and then give an overview of different approaches that have been developed to quantify and model latency of erasure-coded storage. This includes recent work leveraging MDS-Reservation, Fork-Join, Probabilistic, and Delayed-Relaunch scheduling policies, as well as their applications to characterize access latency (e.g., mean, tail, asymptotic latency) of erasure-coded distributed storage systems. We bridge the gap between theory and practice, and discuss lessons learned from prototype implementation. In particular, we will discuss exemplary implementations of erasure-coded storage, illuminate key design degrees of freedom and tradeoffs. Open problems for future research will also be discussed.

Presenter(s):
,

Anoosheh

Heidarzadeh

(Texas A&M University)
Alex

Sprintson

(Texas A&M University)
Abstract:
With the advent of cloud computing, many different types of our data such as medical records, financial transactions, and access logs are stored at remote servers across the globe. This data is being constantly used by a broad range of applications that perform computation remotely for a variety of purposes, including financial reports, statistical analysis, and business analytics. Many of these applications leverage Machine Learning (ML) algorithms for data analysis and decision making. In such applications, it is critical to hide the identity of the data items used in the computation from the cloud operators. We refer to this notion of privacy as data access privacy. The data access privacy provides guarantees to the data owners that the cloud provider does not know whether their data is used by various computing applications. We refer to the process of computation with private data access as private computation. The objective of private computation is to minimize the amount of data that needs to be downloaded from the remote provider(s) while guaranteeing data access privacy. Private computation generalizes classical Private Information Retrieval (PIR) problem by enabling the applications to perform remote computation on the data, and is generally more efficient than first retrieving data privately (using a PIR scheme) and then performing computation on the retrieved data.
Private computation is a fascinating topic with many breakthrough results reported over the recent years by the information and coding theory community. That said, many interesting problems in this field remain open, providing a fertile ground for future research. The goal of this tutorial is to provide a comprehensive survey of the broad range of private computation problems. We discuss both the state-of-the-art achievability schemes and converse proof techniques as well as open research problems. First, we will discuss the Private Linear Computation (PLC) problem and the Private Linear Transformation (PLT) problem whose goal is to compute a single linear combination and multiple linear combinations of a subset of data items, respectively. These problems are motivated by several ML applications including a linear transformation for dimensionality reduction and training linear models for regression or classification. We will discuss several variations of the PLC and PLT problems, which include different types of data access privacy, the presence of side information, the single-provider and multiple-provider scenarios, and the presence of colluding providers. We will also discuss the general private computation scenarios and the related open problems.

Multi-User Information Theory I
Oct 18, 2021

9:00 pm - 9:08 pm (JST)

Author(s):

Kirill

Andreev

(Skoltech)
Pavel

Rybin

(IITP RAS & Skoltech, HSE)
Alexey

A.

Frolov

(Skolkovo Institute of Science and Technology & IITP RAS)
Abstract:

We consider the unsourced random access based on a coded compressed sensing approach. The main idea is to replace the outer tree code proposed by Amalladinne et al. with the code capable of correcting t errors. We derive a finite-length random coding bound for such codes and suggest a practical code construction. We have conducted numerical experiments in the single antenna quasi-static Rayleigh fading MAC. The results show that transition to list-recoverable codes correcting t errors allows performance improvement of coded compressed sensing scheme by 7-10 dB compared to the tree code-based scheme.

9:08 pm - 9:16 pm (JST)

Author(s):

Mehrangiz

Ensan

(Eindhoven University of Technology)
Hamdi

Joudeh

(Eindhoven University of Technology)
Alex

Alvarado

(Eindhoven University of Technology (TU/e))
Ulf

Gustavsson

(Ericsson AB)
Frans

MJ

Willems

(Technical University Eindhoven)
Abstract:

We consider a discrete memoryless cloud radio access network in which K users communicate with a remote destination through 2 relays in a cascade. The relays are oblivious in the sense that they operate without knowledge of the users' codebooks. We focus on a scenario where the first and second relays are connected through a finite-capacity error-free link, while the second relay is connected to the remote destination via an infinite-capacity link. We establish the capacity region in this case, and show that it is achieved via a compress-and-forward scheme with successive decoding. Finally, the extension to Gaussian networks is discussed.

9:16 pm - 9:24 pm (JST)

Author(s):

Homa

Nikbakht

(Inria)
Michele

A

Wigger

(Telecom Paris)
Shlomo (Shitz)

Shamai

(The Technion)
Jean-Marie

Gorce

(INSA-Lyon & CITI, Inria)
Abstract:

This paper analyses the multiplexing gain (MG) achievable over Wyner's symmetric network with random user activity and random arrival of mixed-delay traffic. The mixed-delay traffic is composed of delay-tolerant traffic and delay-sensitive traffic where only the former can benefit from transmitter and receiver cooperation since the latter is subject to stringent decoding delays. The total number of cooperation rounds at transmitter and receiver sides is limited to D rounds. We derive inner and outer bounds on the MG region. In the limit as D \to \infty, the bounds coincide and the results show that transmitting delay-sensitive messages does not cause any penalty on the sum MG. For finite D our bounds are still close and prove that the penalty caused by delay-sensitive transmissions is small.

Machine Learning I
Oct 18, 2021

9:00 pm - 9:08 pm (JST)

Author(s):

Zheng

Wang

(Imperial College London)
Xia

Yili

(Southeast University)
Shanxiang

Lyu

(Jinan University)
Cong

Ling

(Imperial College London)
Abstract:

Sampling from the lattice Gaussian distribution has emerged as a key problem in coding, decoding and cryptography. In this paper, the Gibbs sampling from Markov chain Monte Carlo (MCMC) methods is investigated for lattice Gaussian sampling. Firstly, the error function of random scan Gibbs sampling is derived, and we show that it is partially determined by the selection probabilities over the sampling components. Then, in order to minimize the error function for a better sampling performance, a reinforcement learning mechanism is proposed for random scan Gibbs sampling to adaptively update the selection probabilities by learning from the random samples generated along with the chain. Finally, simulation results based on MIMO detection are presented to confirm the performance gain at the expense of limited complexity cost.

9:08 pm - 9:16 pm (JST)

Author(s):

Talha Cihad

Gulcu

(University of Maryland)
Abstract:

We consider a novel multi-armed bandit setup in which the reward distribution of each arm depends on a single discrete Markov process. This setup involves correlation among arms, as well as correlation among each time instant when one of the arms is pulled. For this problem we show that the cumulative regret has to grow linearly with the number of instances where the outcome of the previous arm pull cannot be determined {\em uniquely}. We propose an algorithm relying on the empirical transition matrix and analyze its performance. The algorithm is shown to ensure that the contribution of regret from time instances where the outcome of the previous arm pull can be identified uniquely is minimized. This implies that the algorithm performs order-wise optimally. We experimentally show that our algorithm can perform better than the correlated-UCB algorithm introduced by Gupta et. al. in 2018 and the classical UCB algorithm.

9:16 pm - 9:24 pm (JST)

Author(s):

Amichai

Painsky

(Tel Aviv University)
Abstract:

The Good-Turing (GT) estimator is perhaps the most popular framework for modelling large alphabet distributions. Classical results show that the GT estimator convergences to the occupancy probability, formally defined as the total probability of words that appear exactly k times in the sample. In this work we introduce new convergence guarantees for the GT estimator, based on worst-case MSE analysis. Our results refine and improve upon currently known bounds. Importantly, we introduce a simultaneous convergence rate to the entire collection of occupancy probabilities.

Polar Codes
Oct 18, 2021

9:00 pm - 9:08 pm (JST)

Author(s):

Charles

Pillet

(Huawei Technologies Co. Ltd.)
Valerio

Bioglio

(France Research Center, Huawei Technologies Co. Ltd.)
Ingmar

Land

(Huawei Technologies France & Paris Research Centre)
Abstract:

In this paper we deal with polar code automorphisms that are beneficial under low-latency automorphism ensemble (AE) decoding, and we propose polar code designs that have such automorphisms. Successive-cancellation (SC) decoding and thus SC-based AE decoding are invariant with respect to the only known polar code automorphisms, namely those of the lower-triangular affine (LTA) group. To overcome this problem, we provide methods to determine whether a given polar code has non-LTA automorphisms and to identify such automorphisms. Building on this, we design specific polar codes that admit automorphisms in the upper-diagonal linear (UTL) group, and thus render SC-based AE decoding effective. Demonstrated by examples, these new polar codes under AE decoding outperform conventional polar codes under SC list decoding in terms of error rate, while keeping the latency comparable to SC decoding. Moreover, state-of-the-art BP-based permutation decoding for polar codes is beaten by BP-based AE thanks to this design.

9:08 pm - 9:16 pm (JST)

Author(s):

Ilya

Dumer

(University of California at Riverside)
Navid

Gharavi

(University of California at Riverside)
Abstract:

We combine polar and LDPC codes to address data correction for various low-power applications. We first use long low-rate LDPC codes that have parity checks of a low weight. Decoding performs several iterations of the belief propagation (BP) algorithm that recalculates the information bits only. Partially corrected bits are then passed to a short polar code that uses successive cancellation list (SCL) decoder. The newly corrected bits then serve as the new inputs for an LDPC decoder. For codes of rate less than 0.1, the algorithm performs on par with a SCL decoder, while substantially reducing decoding complexity and its latency.

9:16 pm - 9:24 pm (JST)

Author(s):

Linghui

Zhou

(KTH Royal Institute of Technology)
Tobias

J.

Oechtering

(KTH Royal Institute of Technology)
Mikael

Skoglund

(KTH Royal Institute of Technology)
Abstract:

In this work, we present a polar code design that offers a provably optimal solution for biometric identification systems allowing authentication under noisy enrollment with secrecy and privacy constraints. Binary symmetric memoryless source and channels are considered. It is shown that the proposed polar code design achieves the fundamental limits and satisfies more stringent secrecy constraints than previously in the literature. The proposed polar code design provides the first example of a code design that achieves the fundamental limits involving both identification and authentication.

Multi-User Information Theory II
Oct 18, 2021

9:30 pm - 9:38 pm (JST)

Author(s):

Abbas

El Gamal

(Stanford University)
Amin

Gohari

(Tehran Institute for Advanced Studies)
Chandra

Nair

(Chinese University of Hong Kong)
Abstract:

This paper studies lower bounds on the capacity of the relay channel with orthogonal receiver components (also referred to as primitive relay channel). We show that the lower bound in Theorem 7 of Cover and El Gamal, which uses mixed decode-forward and compress-forward strategies, is identical to the lower bound of Chong, Motani and Garg, and is always larger than or equal to the recent lower bound of Mondelli, Hassani and Urbanke. We provide a simplified expression for the lower bound in Theorem 7 of Cover and El Gamal and interpret one of its auxiliary variables as implementing the randomized time-sharing strategy. Next, we compare the lower bound for the Gaussian relay channel with orthogonal receiver components to existing upper bounds. Finally, we disprove a conjecture by Ahlswede and Han on the capacity of the subclass of relay channels with orthogonal receiver components and i.i.d. output.

9:38 pm - 9:46 pm (JST)

Author(s):

Gerhard

Kramer

(Technical University of Munich)
Abstract:

Feedback is shown to increase the sum-rate capacity of K-user Gaussian multiple-access channels by at most a factor of approximately 1.54, improving Thomas' doubling bound (1987). The new bound is the best possible in the sense that it can be approached as closely as desired for a massive number of users. Moreover, feedback provides unbounded power gain in K for a fixed transmit power per user.

9:46 pm - 9:54 pm (JST)

Author(s):

Yasutada

Oohama

(University of Electro-Communications)
Bagus

Santoso

()
Abstract:

We pose and investigate the distributed secure source coding based on the common key cryptosystem. This cryptosystem includes the secrecy amplification problem for distributed encrypted sources with correlated keys using post-encryption-compression, which was posed investigated by Santoso and Oohama. In this paper we propose another new security criterion which is generally more strict compared with the commonly used security criterion which is based on the upper-bound of mutual information between the plaintext and the ciphertext. Under this criterion, we establish the necessary and sufficient condition for the secure transmission of correlated sources.

Generative Models
Oct 18, 2021

9:30 pm - 9:38 pm (JST)

Author(s):

Yuta

Nakahara

(Waseda University)
Toshiyasu

Matsushima

(Waseda University)
Abstract:

Explicit assumption of stochastic data generative models is a remarkable feature of lossless compression of general data in information theory. However, current lossless image coding mostly focus on coding procedures without explicit assumption of the stochastic generative model. Therefore, we have difficulty discussing the theoretical optimality of the coding procedure to the stochastic generative model. In this paper, we solve this difficulty by constructing a stochastic generative model by interpreting the previous coding procedure from another perspective. An important problem of our approach is how to learn the hyperparameters of the stochastic generative model because the optimality of our coding algorithm is guaranteed only asymptotically and the hyperparameter setting still affects the expected code length for finite length data. For this problem, we use Bayesian hierarchical modeling and confirm its effect by numerical experiments. In lossless image coding, this is the first study assuming such an explicit stochastic generative model and learning its hyperparameters, to the best of our knowledge.

9:38 pm - 9:46 pm (JST)

Author(s):

Gowtham

R.

Kurri

(Arizona State University)
Tyler

Sypherd

(Arizona State University)
Lalitha

Sankar

(Arizona State University)
Abstract:

We introduce a tunable GAN, called .\alpha.-GAN, parameterized by .\alpha \in (0,\infty]., which interpolates between various .f.-GANs and Integral Probability Metric based GANs (under constrained discriminator set). We construct .\alpha.-GAN using a supervised loss function, namely, .\alpha.-loss, which is a tunable loss function capturing several canonical losses. We show that .\alpha.-GAN is intimately related to the Arimoto divergence, which was first proposed by \"{O}sterriecher (1996), and Liese and Vajda (2006). We posit that the holistic understanding that .\alpha.-GAN introduces will have practical benefits such as convergence and mode collapse.

9:46 pm - 9:54 pm (JST)

Author(s):

Adnan

Rakin

(Arizona State University)
Ye

Wang

(Mitsubishi Electric Research Laboratories)
Shuchin

Aeron

(Tufts University)
Toshiaki

Koike-Akino

(Mitsubishi Electric Research Laboratories (MERL))
Pierre

Moulin

(University of Illinois at Urbana-Champaign)
Kieran

Parsons

(Mitsubishi Electric Research Laboratories)
Abstract:

Adversarial examples have recently exposed the severe vulnerability of neural network models. However, most of the existing attacks require some form of target model information (i.e., weights/model inquiry/architecture) to improve the efficacy of the attack. We leverage the information-theoretic connections between robust learning and generalized rate-distortion theory to formulate a universal adversarial example (UAE) generation algorithm. Our algorithm trains an offline adversarial generator to minimize the mutual information between the label and perturbed data. At the inference phase, our UAE method can efficiently generate effective adversarial examples without high computation cost. These adversarial examples in turn allow for developing universal defenses through adversarial training. Our experiments demonstrate promising gains in improving the training efficiency of conventional adversarial training.

Reed-Muller Codes
Oct 18, 2021

9:30 pm - 9:38 pm (JST)

Author(s):

Wei

Yan

(University of Science and Technology of China)
Sian-Jheng

Lin

(University of Science and Technology of China~(USTC))
Abstract:

Recently, a variant of the Reed-Muller family, called symmetric Reed-Muller codes, was proposed. In this paper, we prove that multivariable symmetric Reed-Muller codes form a class of locally-correctable codes. Then, the dual codes of symmetric Reed-Muller codes are given.

9:38 pm - 9:46 pm (JST)

Author(s):

Renaud-Alexandre

Pitaval

(Huawei Technologies Sweden)
Yi

Qin

(Huawei Technologies Sweden AB)
Abstract:

We consider low-complexity decoding of generalized second-order Reed-Muller frames. Second-order Reed-Muller frames are highly non-coherent, highly-structured, sets of 2^m-dimensional complex vectors with fourth root-of-unity alphabet, that come by design with a low-complexity chirp reconstruction algorithm (ChirpRA). In this paper, we extend ChirpRA to expanded frames in 2^m-dimension with same alphabet, and we also generalized it to Reed-Muller frames in other dimensions constructed from different alphabets.

9:46 pm - 9:54 pm (JST)

Author(s):

Mahdi

Shakiba-Herfeh

(ETIS)
Laura

Luzzi

(ENSEA & CNRS, Université de Cergy-Pontoise)
Arsenia

Chorti

(ETIS UMR 8051, CY University, ENSEA, CNRS & ETIS)
Abstract:

We consider a semi-deterministic wiretap channel where the main channel is noiseless and the eavesdropper's channel is a binary erasure channel (BEC). We provide a lower bound for the achievable secrecy rates of polar and Reed-Muller codes, and compare it to the second order coding rate. To the best of our knowledge, this is the first work which demonstrates the secrecy performance of polar and Reed-Muller codes in short blocklengths. The results show that under a total variation secrecy metric, Reed-Muller codes can achieve secrecy rates very close to the second order approximation rate. On the other hand, we observe a significant gap between the lower bound for the achievable rates of polar codes and the the second order approximation rate for short blocklengths.

Source Coding
Oct 18, 2021

11:00 pm - 11:08 pm (JST)

Author(s):

Wei

Yan

(University of Science and Technology of China)
Sian-Jheng

Lin

(University of Science and Technology of China~(USTC))
Abstract:

Universal coding of integers (UCI) is a class of variable-length code, such that the ratio of the expected codeword length to max{1, H(P)} is within a constant factor, where H(P) is the Shannon entropy of the decreasing probability distribution P. However, if we consider the ratio of the expected codeword length to H(P), the ratio tends to infinity by using UCI, when H(P) tends to zero. To solve this issue, this paper introduces a class of codes, termed generalized UCI, such that the ratio of the expected codeword length to H(P) is within a constant factor K. The definition of generalized UCI is proposed, and then the coding structure of generalized UCI is introduced. Finally, the asymptotically optimal generalized UCI is presented.

11:08 pm - 11:16 pm (JST)

Author(s):

Daisuke

Takeuchi

(Tokyo University of Agriculture and Technology)
Shun

Watanabe

(Tokyo University of Agriculture and Technology)
Abstract:

The achievable rate region of Wyner-Ahlswede-Korner coding problem is investigated for mixed sources. Wyner-Ahlswede-Korner coding problem consists of two encoders and one decoder for two correlated sources. We derive the single-letter formula for mixed sources from Miyake and Kanaya's general result. It clarifies the behaviour of the Wyner-Ahlswede-Korner achievable region for non-ergodic sources; depending on the property of side-information, the achievable regions are different.

11:16 pm - 11:24 pm (JST)

Author(s):

Hoover

H. F.

Yin

(The Chinese University of Hong Kong)
Ka Hei

Ng

(The Chinese University of Hong Kong)
Yu Ting

Shing

(St. Francis Xavier's College)
Russell W. F.

Lai

(Friedrich-Alexander University Erlangen-Nuremberg)
Xishi

Wang

(CUHK)
Abstract:

Although n-channel prefix-free codes are natural extensions of their 1-channel counterpart, the extra dimensions greatly increase the complexity of the problem such that most classical results cannot be generalized directly. Recently, a greedy algorithm was developed for deciding if it is possible to construct a 2-channel prefix-free code from a given multiset of codeword lengths. By dropping the information about codeword assignments which are not necessary for the decision problem, the greedy algorithm runs in polynomial time. However, if we naively turn the decision algorithm into a search algorithm (for constructing a prefix-free code) by retaining the information about codeword assignments, the computational complexity becomes exponential. One puzzle left unsolved was that whether the search problem can also be solved in polynomial time. In this paper, we give an affirmative answer to this question by designing a tailor-made data structure and a new lazy evaluation technique.

ML in Practice
Oct 18, 2021

11:00 pm - 11:08 pm (JST)

Author(s):

Vidhi

Rana

(Wichita State University)
Remi

A

Chou

(Wichita State University)
Abstract:

We design short blocklength codes for the Gaussian wiretap channel under information-theoretic security guarantees. Our approach consists in decoupling the reliability and secrecy constraints in our code design. Specifically, we handle the reliability constraint via an autoencoder, and handle the secrecy constraint via hash functions. For blocklengths smaller than 16, we evaluate through simulations the probability of error at the legitimate receiver and the leakage at the eavesdropper of our code construction. This leakage is defined as the mutual information between the confidential message and the eavesdropper's channel observations, and is empirically measured via a recent mutual information neural estimator. Simulation results provide examples of codes with positive rates that achieve a leakage inferior to one percent of the message length.

11:08 pm - 11:16 pm (JST)

Author(s):

Elsa

Dupraz

(IMT Atlantique)
Lav

R.

Varshney

(University of Illinois at Urbana-Champaign)
François

Leduc-Primeau

(Polytechnique Montreal & IMT Atlantique)
Abstract:

This paper considers Deep Neural Network (DNN) linear-nonlinear computations implemented on memristor crossbar substrates. To address the case where true memristor conductance values may differ from their target values, it introduces a theoretical framework that characterizes the effect of conductance value variations on the final inference computation. With only second-order moment assumptions, theoretical results on tracking the mean, variance, and covariance of the layer-by-layer noisy computations are given. By allowing the possibility of amplifying certain signals within the DNN, power consumption is characterized and then optimized via KKT conditions. Simulation results verify the accuracy of the proposed analysis and demonstrate the significant power efficiency gains that are possible via optimization for a target mean squared error.

Streaming Codes I
Oct 18, 2021

11:00 pm - 11:08 pm (JST)

Author(s):

Myna

Vajha

(Indian Institute of Science)
Vinayak

Ramkumar

(Indian Institute of Science)
Mayank

Jhamtani

(Indian Institute of Science, Bangalore)
P Vijay

Kumar

(Indian Institute of Science & University of Southern California)
Abstract:

The Gilbert-Elliot (GE) channel is a commonly-accepted model for packet erasures in networks. Streaming codes are a class of packet-level erasure codes designed to provide reliable communication over the GE channel. The design of a streaming code may be viewed as a two-step process. In the first, a more tractable, delay-constrained sliding window (DCSW) channel model is considered as a proxy to the GE channel. The streaming code is then designed to reliably recover from all erasures introduced by the DCSW channel model. Simulation is typically used to evaluate the performance of the streaming code over the original GE channel, as analytic performance evaluation is challenging. In the present paper, we take an important first step towards analytical performance evaluation. Recognizing that most, efficient constructions of a streaming code are based on the diagonal embedding or horizontal embedding of scalar block codes within a packet stream, this paper provides upper and lower bounds on the block-erasure probability of the underlying scalar block code when operated over the GE channel.

11:08 pm - 11:16 pm (JST)

Author(s):

Nikhil Krishnan

Muralee Krishnan

(International Institute of Information Technology Bangalore)
Gustavo

Facenda

(Universidade Federal de Santa Catarina)
Elad

Domanovitz

(University of Toronto)
Ashish

Khisti

(University of Toronto)
Wai-Tian

Tan

(Cisco Systems)
John

Apostolopoulos

(Cisco Systems)
Abstract:

In this paper, we investigate streaming codes over a three-node relay network. Source node transmits a sequence of message packets to the destination via a relay. Source-to-relay and relay-to-destination links are unreliable and introduce at most N_1 and N_2 packet erasures, respectively. Destination needs to recover each message packet with a strict decoding delay constraint of T time slots. We propose streaming codes under this setting for all feasible parameters \{N_1, N_2, T\}. Relay naturally observes erasure patterns occurring in the source-to-relay link. In our code construction, we employ a channel-state-dependent relaying strategy, which rely on these observations. In a recent work, Fong et al. provide streaming codes featuring channel-state-independent relaying strategies, for all feasible parameters \{N_1, N_2, T\}. Our schemes offer a strict rate improvement over the schemes proposed by Fong et al., whenever N_1

11:16 pm - 11:24 pm (JST)

Author(s):

Shobhit

Bhatnagar

(Indian Institute of Science)
Biswadip

Chakraborti

(INDIAN INSTITUTE OF SCIENCE BANGALORE)
P Vijay

Kumar

(Indian Institute of Science & University of Southern California)
Abstract:

Streaming codes may be regarded as packet-level convolutional codes that guarantee recovery from packet erasures under a strict decoding-delay constraint and are hence relevant to the low-latency objective of many modern communication systems. Past study of these codes has focused on performance over a tractable approximation of the Gilbert-Elliott channel model, known as the delay-constrained sliding window (DCSW) channel model. Under the DCSW channel model, within any sliding window of length w there can either be (i) a burst of at most b packet erasures or (ii) at most a random packet erasures. We study here, an extended version of the first constraint which permits e random erasures in addition to a burst of b erasures. We show that the capacity of this extended DCSW channel is strictly less than that of the corresponding DCSW channel in which b is replaced by b + e. Cyclic codes are easy to implement and are inherently well-suited to burst-erasure recovery. We identify a necessary and sufficient condition on the parity polynomial of an [n, k] cyclic code that allows the code to recover from any burst of n − k − s erasures along with any ρ random erasures, 1 ≤ ρ ≤ s ≤ n − k. We use this result to construct cyclic codes that provide reliable communication over the extended DCSW channel for certain parameters.

Streaming Codes II
Oct 18, 2021

11:30 pm - 11:38 pm (JST)

Author(s):

Elad

Domanovitz

(University of Toronto)
Gustavo

Facenda

(Universidade Federal de Santa Catarina)
Ashish

Khisti

(University of Toronto)
Wai-Tian

Tan

(Cisco Systems)
John

Apostolopoulos

(Cisco Systems)
Abstract:

We study the problem of transmitting a sequence of messages (streaming messages) through a multi-link, multi-hop packet erasure network. Each message must be reconstructed in-order and under a strict delay constraint. Special cases of our setting with a single link on each hop have been studied recently - the case of a single relay-node, is studied in Fong et al [1]; the case of multiple relays, is studied in Domanovitz et al [2]. As our main result, we propose an achievable rate expression that reduces to previously known results when specialized to their respective settings. Our proposed scheme is based on the idea of concatenating single-link codes from [2] in a judicious manner to achieve the required delay constraints. We propose a systematic approach based on convex optimization to maximize the achievable rate in our framework.

11:38 pm - 11:46 pm (JST)

Author(s):

Vinayak

Ramkumar

(Indian Institute of Science)
Myna

Vajha

(Indian Institute of Science)
P Vijay

Kumar

(Indian Institute of Science & University of Southern California)
Abstract:

Streaming codes are a class of packet-level erasure codes that are designed with the goal of ensuring recovery in low-latency fashion, of erased packets over a communication network. It is well-known in the streaming code literature, that diagonally embedding codewords of a \([\tau+1,\tau+1-a]\) Maximum Distance Separable (MDS) code within the packet stream, leads to rate-optimal streaming codes capable of recovering from \(a\) arbitrary packet erasures, under a strict decoding delay constraint \(\tau\). Thus MDS codes are geared towards the efficient handling of the worst-case scenario corresponding to the occurrence of \(a\) erasures. In the present paper, we have an increased focus on the efficient handling of the most-frequent erasure patterns. We study streaming codes which in addition to recovering from \(a>1\) arbitrary packet erasures under a decoding delay \(\tau\), have the ability to handle the more common occurrence of a single-packet erasure, while incurring smaller delay \(r<\tau\). We term these codes as \((a, \tau, r)\) locally recoverable streaming codes (LRSCs), since our single-erasure recovery requirement is similar to the requirement of locality in a coded distributed storage system. We characterize the maximum possible rate of an LRSC by presenting rate-optimal constructions for all possible parameters \(\{a, \tau, r\}\). Although the rate-optimal LRSC construction provided in this paper requires large field size, the construction is explicit. It is also shown that our \((a, \tau=a(r+1)-1, r)\) LRSC construction provides the additional guarantee of recovery from the erasure of \(h, 1 \leq h \leq a,\) packets, with delay \(h(r+1)-1\). The construction thus offers graceful degradation in decoding delay with increasing number of erasures.

Lossy Compression
Oct 18, 2021

11:30 pm - 11:38 pm (JST)

Author(s):

Chak Fung

Choi

(The Chinese University of Hong Kong)
Cheuk Ting

Li

(The Chinese University of Hong Kong)
Abstract:

We consider a variant of the channel simulation problem with a single input and multiple outputs, where Alice observes a probability distribution \(P\) from a set of prescribed probability distributions \(\mathbb{\mathcal{P}}\), and sends a prefix-free codeword \(W\) to Bob to allow him to generate \(n\) i.i.d. random variables \(X_{1}, X_{2}, .., X_{n}\) which follow the distribution \(P\). This can also be regarded as a lossy compression setting for probability distributions. This paper describes encoding schemes for three cases of \(P\): \(P\) is a distribution over positive integers, \(P\) is a continuous distribution over \([0, 1]\) with a non-increasing pdf, and \(P\) is a continuous distribution over \([0, \infty)\) with a non-increasing pdf. We show that the growth rate of the expected codeword length is sub-linear in \(n\) when a power law bound is satisfied. An application of multiple-outputs channel simulation is the compression of probability distributions.

11:38 pm - 11:46 pm (JST)

Author(s):

Rony

Bou Rouphael

(ETIS UMR 8051, CY Cergy Paris University, CNRS)
Mael

Le Treust

(ETIS UMR 8051, Université Cergy-Pontoise, ENSEA, CNRS)
Abstract:

We study the multi-user Bayesian persuasion game between one encoder and two decoders, where the first decoder is better informed than the second decoder. We consider two perfect links, one to the first decoder only, and the other to both decoders. We consider that the encoder and both decoders are endowed with distinct and arbitrary distortion functions. We investigate the strategic source coding problem in which the encoder commits to an encoding while the decoders select the sequences of symbols that minimize their long-run respective distortion functions. We characterize the optimal encoder distortion value by considering successive refinement coding with respect to a specific probability distribution which involves two auxiliary random variables, and captures the incentive constraints of both decoders.

11:46 pm - 11:54 pm (JST)

Author(s):

Hui-An

Shen

(University of Bern)
Stefan

M.

Moser

(ETH Zurich & National Chiao Tung University (NCTU))
Jean-Pascal

Pfister

(University of Bern)
Abstract:

We study rate-distortion problems of a Poisson process using a group theoretic approach. By describing a realization of a Poisson point process with either point timings or inter-point intervals and by choosing appropriate distortion measures, we establish rate-distortion problems of a homogeneous Poisson process as ball- or sphere-covering problems for realizations of the hyperoctahedral group in .\Reals^n.. Specifically, the realizations we investigate are a hypercube and a hyperoctahedron. Thereby we unify three known rate-distortion problems of a Poisson process (with different distortion measures, but resulting in the same rate-distortion function) with the Laplacian-.\ell_1. rate-distortion problem.

Stochastic Block Models
Oct 19, 2021

9:00 pm - 9:08 pm (JST)

Author(s):

Eli

Chien

(University of Illinios Urbana-Champaign)
Pan

Li

(Purdue University)
Olgica

Milenkovic

(University of Illinois at Urbana-Champaign (UIUC))
Abstract:

The landing probability of a vertex in a hypergraph is the probability of a random walk ending at the vertex after making a prescribed number of steps. Landing probabilities are of importance for a number of learning tasks on hypergraphs, including higher-order PageRanks and (local) community detection. We perform the first mean-field study of landing probabilities of random walks on hypergraphs and examine clique-expansion and tensor-based methods. In particular, we evaluate the mean-field characteristics of the two methods over a class of random hypergraph models for the task of seed-set community expansion. We determine parameter regimes in which one method outperforms the other and propose a new hybrid expansion method termed "partial clique-expansion" to reduce the projection distortion and reduce the complexity of tensor-based methods on partially expanded hypergraphs.

9:08 pm - 9:16 pm (JST)

Author(s):

Feng

Zhao

(Graduate School at Shenzhen, Tsinghua University)
Jin

Sima

(California Institute of Technology)
Shao-Lun

Huang

(Tsinghua-Berkeley Shenzhen Institute)
Abstract:

Side information improves the accuracy in community detection problems. While experimental results demonstrate the superior performance of many detection methods based on both the node attributes and graph structure, the question of the fundamental limit of the error rate for exact recovery remains open. In this paper, we obtain the asymptotic optimal error rate in the sense of exact recovery for a special two-community symmetric stochastic block model (SSBM) with side information consisting of multiple features. Our result provides insight on the number of features and nodes in the graph needed for community detection.

9:16 pm - 9:24 pm (JST)

Author(s):

Jin

Sima

(California Institute of Technology)
Feng

Zhao

(Graduate School at Shenzhen, Tsinghua University)
Shao-Lun

Huang

(Tsinghua-Berkeley Shenzhen Institute)
Abstract:

The role that side information plays in improving the exact recovery threshold in the stochastic block model (SBM) has been studied in many aspects. This paper studies exact recovery in n node balanced binary symmetric SBM with side information, given in the form of O(log n) i.i.d. samples at each node. A sharp exact recovery threshold is obtained and turns out to coincide with an existing threshold result, where no balanced constraint is imposed. Our main contribution is an efficient semi-definite programming (SDP) algorithm that achieves the optimal exact recovery threshold. Compared to the existing works on SDP algorithm for SBM with constant number of samples as side information, the challenge in this paper is to deal with the number of samples increasing in n.

Coding and Caching
Oct 19, 2021

9:00 pm - 9:08 pm (JST)

Author(s):

Pooja Nayak

Muralidhar

(Indian Institute of Science Bangalore)
Digvijay

Katyal

(Indian Institute of Science Bangalore)
B. Sundar

Rajan

(Indian Institute of Science)
Abstract:

The well known Maddah-Ali-Niesen (MAN) coded caching scheme for users with dedicated cache is extended for use in multi-access coded cache scheme where the number of users need not be same as the number of caches in the system. The well known MAN scheme is recoverable as a special case of the multi-access system considered. The performance of this scheme is compared with the existing works on multi-access coded caching. To be able to compare the performance of different multi-access schemes with different number of users for the same number of caches, the terminology of per user rate (rate divided by the number of users) introduced in \cite{KNS} is used.

9:08 pm - 9:16 pm (JST)

Author(s):

Pooja Nayak

Muralidhar

(Indian Institute of Science Bangalore)
Digvijay

Katyal

(Indian Institute of Science Bangalore)
B. Sundar

Rajan

(Indian Institute of Science)
Abstract:

Recently multi-access coded caching schemes with number of users different from the number of caches obtained from a special case of resolvable designs called Cross Resolvable Designs (CRDs) have been reported and a new performance metric called rate-per-user has been introduced [8]. In this paper we present a generalization of this work resulting in multi-access coded caching schemes with improved rate-per-user.

9:16 pm - 9:24 pm (JST)

Author(s):

K. K. Krishnan

Namboodiri

(Indian Institute of Science)
B. Sundar

Rajan

(Indian Institute of Science)
Abstract:

The multi-access variant of the coded caching problem in the presence of an external wiretapper is investigated . A multi-access coded caching scheme with $K$ users, K caches and N files, where each user has access to L neighbouring caches in a cyclic wrap-around manner, is proposed, which is secure against the wiretappers. Each transmission in the conventional insecure scheme will be now encrypted by a random key. The proposed scheme uses a novel technique for the key placement in the caches. It is also shown that the proposed secure multi-access coded caching scheme is within a constant multiplicative factor from the information-theoretic optimal rate for .L\geq \frac{K}{2}. and .N\geq 2K..

9:24 pm - 9:32 pm (JST)

Author(s):

Pruthvi

Trinadh

(Indian Institute of Technology Bhubaneswar)
Monolina

Dutta

(Indian Institute of Technology Bhubaneswar)
Anoop

Thomas

(Indian Institute of Technology Bhubaneswar)
B. Sundar

Rajan

(Indian Institute of Science)
Abstract:

Data traffic in a client-server framework exhibits a temporal variability leading to congestion of resources at peak hours. One prevalent technique to overcome this problem is to load popular content/data into cache memories distributed across the end users. In this paper, the multi-access coded caching problem is considered in which each client is connected to multiple consecutive caches in a cyclic wrap around fashion and the cache memories are arbitrarily loaded in a decentralized manner. A new delivery scheme is proposed for the decentralized multi-access coded caching problem. A lower bound on the delivery rate is also obtained for the decentralized multi-access coded caching problem using techniques from index coding. The delivery scheme is shown to be optimal among all linear schemes when the number of caches associated with each user satisfies certain constraints.

Wiretap Channel
Oct 19, 2021

9:00 pm - 9:08 pm (JST)

Author(s):

Morteza

Shoushtari

(Brigham Young University)
Willie

K

Harrison

(Brigham Young University)
Abstract:

In this paper, we consider the equivocation of finite blocklength coset codes when used over binary erasure wiretap channels. We make use of the equivocation matrix in comparing codes that are suitable for scenarios with noisy channels for both the intended receiver and an eavesdropper. Equivocation matrices have been studied in the past only for the binary erasure wiretap channel model with a noiseless channel for the intended recipient. In that case, an exact relationship between the elements of equivocation matrices for a code and its dual code was identified. The majority of work on coset codes for wiretap channels only addresses the noise-free main channel case, and extensions to noisy main channels require multi-edge type codes. In this paper, we supply a more insightful proof for the noiseless main channel case, and identify a new dual relationship that applies when two-edge type coset codes are used for the noisy main channel case. The end result is that the elements of the equivocation matrix for a dual code are known precisely from the equivocation matrix of the original code according to fixed reordering patterns. Such relationships allow one to study the equivocation of codes and their duals in tandem, which simplifies the search for best and/or good finite blocklength codes of various sizes. This paper is the first work that succinctly links the equivocation/error correction capabilities of dual codes for two-edge type coset coding over erasure-prone main channels.

9:08 pm - 9:16 pm (JST)

Author(s):

Aria

Nouri

(Shahid Beheshti University)
Reza

Asvadi

(Shahid Beheshti University)
Jun

Chen

(McMaster University)
Pascal

Vontobel

(The Chinese University of Hong Kong)
Abstract:

We consider reliable and secure communication over intersymbol interference wiretap channels (ISI-WTCs). In particular, we first examine the setup where the source at the input of an ISI-WTC is unconstrained and then, based on a general achievability result for arbitrary wiretap channels, we derive an achievable secure rate for this ISI-WTC. Afterwards, we examine the setup where the source at the input of an ISI-WTC is constrained to be a finite-state machine source (FSMS) of a certain order and structure. Optimizing the parameters of this FSMS toward maximizing the secure rate is a computationally intractable problem in general, and so, toward finding a local maximum, we propose an iterative algorithm that at every iteration replaces the secure rate function by a suitable surrogate function whose maximum can be found efficiently.

9:16 pm - 9:24 pm (JST)

Author(s):

Luca

Barletta

(Politecnico di Milano)
Alex

Dytso

(New Jersey Institute of Technology)
Abstract:

This work studies the secrecy-capacity of a scalar-Gaussian wiretap channel with an amplitude constraint on the input. It is known that for this channel, the secrecy-capacity-achieving distribution is discrete with finitely many points. This work improves such result by showing an upper bound of the order ..\frac{A}{\sigma_1^2}.. where ..A.. is the amplitude constraint and ..\sigma_1^2.. is the variance of the Gaussian noise over the legitimate channel.

Information Theory and Statistics
Oct 19, 2021

9:40 pm - 9:48 pm (JST)

Author(s):

Mehdi

Molkaraie

(University of Toronto)
Abstract:

The dual normal factor graph and the factor graph duality theorem have been considered for discrete graphical models. In this paper, we show an application of the factor graph duality theorem to continuous graphical models. Specifically, we propose a method to solve exactly the Gaussian graphical models defined on the ladder graph if certain conditions on the local covariance matrices are satisfied. Unlike the conventional approaches, the efficiency of the method depends on the position of the zeros in the local covariance matrices. The method and details of the dualization are illustrated on two toy examples.

9:48 pm - 9:56 pm (JST)

Author(s):

Alex

Dytso

(New Jersey Institute of Technology)
Martina

Cardone

(University of Minnesota)
Abstract:

Consider a pair of random vectors \( (\mathbf{X},\mathbf{Y}) \) and the conditional expectation operator \( \mathbb{E}[\mathbf{X}|\mathbf{Y}=\mathbf{y}] \). This work studies analytic properties of the conditional expectation by characterizing various derivative identities. The paper consists of two parts. In the first part of the paper, a general derivative identity for the conditional expectation is derived. Specifically, for the Markov chain \( \mathbf{U} \leftrightarrow \mathbf{X} \leftrightarrow \mathbf{Y} \), a compact expression for the Jacobian matrix of \( \mathbb{E}[\mathbf{U}|\mathbf{Y} = \mathbf{y}] \) is derived. In the second part of the paper, the main identity is specialized to the exponential family. Moreover, via various choices of the random vector \(\mathbf{U}\), the new identity is used to recover and generalize several known identities and derive some new ones. As a first example, a connection between the Jacobian of \(\mathbb{E}[\mathbf{X}|\mathbf{Y}=\mathbf{y}]\) and the conditional variance is established. As a second example, a recursive expression between higher order conditional expectations is found, which is shown to lead to a generalization of the Tweedy's identity. Finally, as a third example, it is shown that the \(k\)-th order derivative of the conditional expectation is proportional to the \((k+1)\)-th order conditional cumulant.

9:56 pm - 10:04 pm (JST)

Author(s):

Hao-Chung

Cheng

(National Taiwan University)
Baris

Nakiboglu

(Middle East Technical University)
Abstract:

The existence of a unique Augustin mean and its invariance under the Augustin operator are established for arbitrary input distributions with finite Augustin information for channels with countably generated output σ-algebras. The existence is established by representing the conditional Rényi divergence as a lower semicontinuous and convex functional in an appropriately chosen uniformly convex space and then invoking the Banach-Saks property in conjunction with the lower semicontinuity and the convexity. A new family of operators is proposed to establish the invariance of the Augustin mean under the Augustin operator for orders greater than one. Some members of this new family strictly decrease the conditional Rényi divergence, when applied to the second argument of the divergence, unless the second argument is a fixed point of the Augustin operator.

Codes for Storage
Oct 19, 2021

9:40 pm - 9:48 pm (JST)

Author(s):

Ting-Yi

Wu

(Huawei Technologies Co., Ltd.)
Yunghsiang

Sam

Han

(Dongguan University of Technology)
Zhengrui

Li

(Hong Kong University of Science and Technology)
Bo

Bai

(Huawei Technologies Co., Ltd.)
Gong

Zhang

(Huawei Technologies Co., Ltd.)
Xiaoyang

Zhang

(Huawei Technologies Co., Ltd.)
Xiang

Wu

(Huawei Technologies Co., Ltd.)
Abstract:

Regenerating codes are designed to reduce the repair bandwidth (access bandwidth) for rebuilding a fail node in an erasure-coded storage system. In practical systems, the fail node is not rebuilt immediately. Before its rebuilding, the data originally stored in the failed node might be accessed by the system. Hence, accessing the data in the failed disk (degraded read) with low latency is crucial for any practical storage system. In this work, to solve this problem, a new class of the regenerating codes based on the maximum distance separable (MDS) array codes is defined, named the MDS array code with the property of degraded read friendly (DRF). For the DRF MDS array codes with 2 redundant nodes and the sub-packetization level of 2, the lower bound of their access bandwidth is derived. A class of the DRF MDS array codes that achieves the derived bound is given to solidify the achievability of the proposed lower bound.

9:48 pm - 9:56 pm (JST)

Author(s):

Zhengrui

Li

(Hong Kong University of Science and Technology)
Yunghsiang

Sam

Han

(Dongguan University of Technology)
Ting-Yi

Wu

(Huawei Technologies Co., Ltd.)
Hanxu

Hou

(Dongguan University of Technology)
Bo

Bai

(Huawei Technologies Co., Ltd.)
Gong

Zhang

(Huawei Technologies Co., Ltd.)
Abstract:

In this paper, we consider two rack-aware storage systems. First, large-scale rack-aware storage system, which is very common in large-scale storage system, is a rack-aware storage system where all sizes of racks are at least the number of redundant nodes. For such storage system, we prove that any Maximum Distance Separable (MDS) codes can have optimal inter-rack repair bandwidth and give a closed-form representation of all repair schemes with optimal inter-rack repair bandwidth. Furthermore, we show that the optimal repair access and optimal inter-rack repair bandwidth can be attained simultaneously for such storage system. Second, we investigate the rack-aware storage system of all racks with the same size, which is called uniform rack-aware storage system. We prove that, except the trivial cases, we cannot attain optimal inter-rack repair bandwidth and optimal repair access for such storage system at the same time. Specifically, we establish the lower bound of repair access for a repair scheme with optimal inter-rack repair bandwidth, which is tight for some parameters, and also the tight lower bound of inter-rack repair bandwidth for a repair scheme with optimal repair access.

9:56 pm - 10:04 pm (JST)

Author(s):

Bing

Zhu

(Central South University)
Shigeng

Zhang

(Central South University)
Weiping

Wang

(Central South University)
Abstract:

Modern distributed storage systems are increasingly implementing erasure codes to obtain better storage performance. In such systems, it is desirable to regenerate a failed storage node in a cost-effective manner since node failures occur frequently in real-world storage networks. Fractional repetition (FR) codes are a special class of regenerating codes that enable efficient recovery of failed storage nodes. In this paper, we introduce expandable FR codes, wherein both the number of storage nodes and the capacity of each node in the storage systems can be readily expanded. We present explicit constructions of expandable FR codes by applying two families of combinatorial structures called embeddable quasi-residual designs and extendible t-designs. Moreover, we study the property of constructed codes for some special scenarios.

Covert Communication
Oct 19, 2021

9:40 pm - 9:48 pm (JST)

Author(s):

Vidyalaxmi

Dani

(IIT Madras)
Venkatesh

Ramaiyan

(Indian Institute of Technology Madras)
Devendra

Jalihal

(Indian Institute of Technology Madras)
Abstract:

We study a problem of covert communication over binary symmetric channels (BSC) in an asynchronous setup. Here, Alice seeks to communicate to Bob over a BSC while trying to be covert with respect to Willie, who observes any communication through possibly a different BSC. When Alice communicates, she transmits a message (using a codeword of length n) at a random time uniformly distributed in a window of size A_w slots. We assume that Bob has side information about the time of transmission leading to a reduced uncertainty of A_b slots for Bob, where A_b < A_w. In this setup, we seek to characterize the limits of covert communication as a function of the timing advantage. When A_w is increasing exponentially in n, we characterize the covert capacity as a function of A_w and A_b. When A_w is increasing sub-exponentially in n, we characterize lower and upper bounds on achievable covert bits and show that positive covert rates are not feasible irrespective of timing advantage. Using numerical work, we illustrate our results for different network scenarios, and also highlight a tradeoff between timing advantage and channel advantage (between Bob and Willie).

9:48 pm - 9:56 pm (JST)

Author(s):

Meng-Che

Chang

(Georgia Institute of Technology)
Matthieu

Bloch

(Georgia Institute of Technology)
Abstract:

We consider the problem of covert sequential testing, in which a legitimate party attempts to run a sequential test while escaping detection from an adversary.Specifically, the legitimate party's decisions should meet prescribed risk constraints and, simultaneously, the adversary's observations induced by the test should remain indistinguishable from the observations obtained in the absence of a test. Our main result is the characterization of the risk exponentγθ, which captures the asymptotic exponential decrease of the risk with the square-root of the averaged stopping time in the limit of low risk.An example is provided to illustrate how the covertness constraint influences the design of the sequential test.

9:56 pm - 10:04 pm (JST)

Author(s):

Arti

Yardi

(International Institute of Information Technology (IIIT) Bangalore)
Tejas

Bodas

(TCS Research)
Abstract:

Based on the covert communication framework, we consider a covert queueing problem that has a Markovian statistic. Willie jobs arrive according to a Poisson process and require service from server Bob. Bob does not have a queue for jobs to wait and hence when the server is busy, arriving Willie jobs are lost. Willie and Bob enter a contract under which Bob should only serve Willie jobs. As part of the usage statistic, for a sequence of N consecutive jobs that arrived, Bob informs Willie whether each job was served or lost (this is the Markovian statistic). Bob is assumed to be violating the contract and admitting non-Willie (Nillie) jobs according to a Poisson process. For such a setting, we identify the hypothesis testing to be performed (given the Markovian data) by Willie to detect the presence or absence of Nillie jobs. We also characterize the upper bound on arrival rate of Nillie jobs such that the error in the hypothesis testing of Willie is arbitrarily large, ensuring covertness in admitting Nillie jobs.

Age of Information
Oct 19, 2021

11:00 pm - 11:08 pm (JST)

Author(s):

Jixiang

Zhang

(Southeast University & School of Information Science and Technology)
Yinfei

Xu

(Southeast University)
Abstract:

In this paper, we consider the age of information (AoI) of a discrete time status updating system, focusing on finding the stationary AoI distribution assuming that the Ber/G/1/1 queue is used. Following the standard queueing theory, we show that by invoking a two-dimensional state vector which tracks the AoI and packet age in system simultaneously, the stationary AoI distribution can be derived by analyzing the steady state of the constituted two-dimensional stochastic process. We give the general formula of the AoI distribution and calculate the explicit expression when the service time is also geometrically distributed. The discrete and continuous AoI are compared, we depict the mean of discrete AoI and that of continuous time AoI for system with M/M/1/1 queue. Although the stationary AoI distribution of some continuous time single-server system has been determined before, in this paper, we shall prove that the standard queueing theory is still appliable to analyze the discrete AoI, which is even stronger than the proposed methods handling the continuous AoI.

11:08 pm - 11:16 pm (JST)

Author(s):

Mohammad

Moltafet

(University of Oulu)
Markus

Leinonen

(University of Oulu)
Marian

Codreanu

(Linkoping University)
Abstract:

We consider a multi-source status update system in which status updates are transmitted as packets containing the measured value of the monitored process and a time stamp representing the time when the sample was generated. The packets of each source are generated according to a Poisson process and served according to an exponentially distributed service time. We assume that the received status update packets need further processing before being used (hence, computation-intensive). This is mathematically modeled by an additional server at the sink. The sink server serves the packets according to an exponentially distributed service time. We introduce two packet management policies, a preemptive policy and a blocking policy, and derive the moment generating function (MGF) of the AoI of each source under the both policies. In the both policies, the system can contain at most two packets, one at the transmitter server and one at the sink server. In the preemptive policy, a new arriving packet preempts any possible packet that is currently under service regardless of the packet's source index. In the blocking policy, when a server is busy at the arrival instant of a packet, the arriving packet is blocked and cleared. We assume that the same preemptive/blocking policy is employed in both the transmitter and sink server. Numerical results are provided to assess the results.

11:16 pm - 11:24 pm (JST)

Author(s):

Yunus

Inan

(EPFL)
Reka

Inovan

(EPFL)
Emre

Telatar

(EPFL)
Abstract:

We propose a simple model to study the tradeoff between timeliness and distortion, where different pieces of data have a different cost of not being sent. We pose the question of finding the optimal tradeoff as a policy design problem amenable to dynamic programming methods. We study the structural properties of optimal transmission policies, give an algorithmic procedure to find the optimal tradeoff, and numerically evaluate some instances.

Codes for Distributed Computing
Oct 19, 2021

11:00 pm - 11:08 pm (JST)

Author(s):

Amogh

Johri

(International Institute of Information Technologh Bangalore)
Arti

Yardi

(International Institute of Information Technology (IIIT) Bangalore)
Tejas

Bodas

(TCS Research)
Abstract:

In distributed machine learning (DML), the training data is distributed across multiple worker nodes to perform the underlying training in parallel. One major problem affecting the performance of DML algorithms is presence of stragglers. These are nodes that are terribly slow in performing their task which results in under-utilization of the training data that is stored in them. Towards this, gradient coding mitigates the impact of stragglers by adding sufficient redundancy in the data. Gradient coding and other straggler mitigation schemes assume that the straggler behavior of the worker nodes is identical. Our experiments on the Amazon AWS cluster however suggest otherwise and we see that there is a correlation in the straggler behavior across iterations. To model this, we introduce a heterogeneous straggler model where nodes are categorized into two classes, slow and active. To better utilize training data stored with slow nodes, we modify the existing gradient coding schemes with shuffling of the training data among workers. Our results (both simulation and cloud experiments) suggest remarkable improvement with shuffling over existing schemes. We perform theoretical analysis for the proposed models justifying their utility.

11:08 pm - 11:16 pm (JST)

Author(s):

Ruowan

Ji

(Texas A&M University)
Asit

Kumar

Pradhan

(Texas A&M University)
Anoosheh

Heidarzadeh

(Texas A&M University)
Krishna

Narayanan

(Texas A&M University)
Abstract:

We introduce a class of codes, called Squeezed Random Khatri-Rao Product (RKRP) codes, for coded matrix multiplication when each worker node can perform multiple submatrix products. The proposed codes are a generalization of RKRP codes in [1] and are built on the idea of squeezed polynomial codes in [2]. We show that squeezed RKRP codes are maximum distance separable with probability 1. They have the same communication cost as that of squeezed polynomial codes while offering better numerical stability.

11:16 pm - 11:24 pm (JST)

Author(s):

Junge

Wang

(University of California, Irvine & Center for Pervasive Communications and Computing)
Zhuqing

Jia

(Beijing University of Posts and Telecommunications)
Syed

Ali

Jafar

(University of California Irvine)
Abstract:

Coded distributed matrix multiplication (CDMM) schemes, such as MatDot codes, seek efficient ways to distribute matrix multiplication task(s) to a set of N distributed servers so that the answers returned from any R servers are sufficient to recover the desired product(s). For example, to compute the product of matrices U; V, MatDot codes partition each matrix into p > 1 sub-matrices to create smaller coded computation tasks that reduce the upload/storage at each server by 1/p, such that UV can be recovered from the answers returned by any R = 2p−1 servers. An important concern in CDMM is to reduce the recovery threshold R for a given storage/upload constraint. Recently, Jeong et al. introduced Approximate MatDot (AMD) codes that are shown to improve the recovery threshold by a factor of nearly 2, from 2p − 1 to p. A key observation that motivates our work is that the storage/upload required for approximate computing depends not only on the dimensions of the (coded) sub-matrices that are assigned to each server, but also on their precision levels - a critical aspect that is not explored by Jeong et al. Our main contribution is a dimensional analysis of AMD codes inspired by the Generalized Degrees of Freedom (GDoF) framework previously developed for wireless networks, which indicates that for the same upload/storage, once the precision levels of the task assignments are accounted for, AMD codes surprisingly fall short in all aspects of even the trivial replication scheme which assigns the full computation task to every server. The dimensional analysis is supported by simple numerical experiments.

Information Privacy
Oct 19, 2021

11:00 pm - 11:08 pm (JST)

Author(s):

Borja

Rodríguez-Gálvez

(KTH Royal Institute of Technology)
Ragnar

Thobaben

(KTH Royal Institute of Technology)
Mikael

Skoglund

(KTH Royal Institute of Technology)
Abstract:

In this article, we propose a new variational approach to learn private and/or fair representations. This approach is based on the Lagrangians of a new formulation of the privacy and fairness optimization problems that we propose. In this formulation, we aim to generate representations of the data that keep a prescribed level of the relevant information that is not shared by the private or sensitive data, while minimizing the remaining information they keep. The proposed approach (i) exhibits the similarities of the privacy and fairness problems, (ii) allows us to control the trade-off between utility and privacy or fairness through the Lagrange multiplier parameter, and (iii) can be comfortably incorporated to common representation learning algorithms such as the VAE, the beta-VAE, the VIB, or the nonlinear IB.

11:08 pm - 11:16 pm (JST)

Author(s):

Anoosheh

Heidarzadeh

(Texas A&M University)
Alex

Sprintson

(Texas A&M University)
Abstract:

This paper considers the problem of single-server Individually-Private Information Retrieval (IPIR). In this problem, a user wants to retrieve \(D\) messages belonging to a dataset of \(K\) messages stored on a single server. Initially, the user knows \(M\) other messages belonging to the dataset as side information, where the identities of these \(M\) messages are unknown to the server. The goal is to minimize the total amount of information that the user must download from the server while keeping the identity of each of the \(D\) desired messages individually private, i.e., the identity of every individual message wanted by the user must be protected. The capacity of IPIR, which is defined as the supremum of all achievable download rates, was previously characterized for \(D=2, M=1\). However, the capacity was left open for all other values of \(D, M\). In this work, we present a technique for the proof of converse, based on a novel combinatorial approach. Using this technique, we establish an upper bound on the capacity of IPIR for \(D=2, M=2\). For this setting, we also propose a new IPIR scheme---based on a probabilistic partitioning of the messages, that achieves the capacity upper bound. We believe that our approach can be employed for proving the converse and designing optimal schemes for the general cases of the problem.

11:16 pm - 11:24 pm (JST)

Author(s):

Akira

Kamatsuka

(Shonan Institute of Technology)
Takahiro

Yoshida

(Nihon University)
Toshiyasu

Matsushima

(Waseda University)
Abstract:

We consider the problem of publishing data with utility and privacy guarantees in a statistical decision-theoretical framework. In this framework, we introduce a statistical decision-theoretic quantity called average gain for measuring not only privacy but also utility. We also show a relationship between the average gain and the α-leakage, a tunable leakage measure proposed by Liao et al. Moreover, we formulate the privacy-utility trade-off (PUT) problem using Stratonovich's value of information (VoI) and present an analysis of the PUT.

Hypothesis Testing
Oct 19, 2021

11:30 pm - 11:38 pm (JST)

Author(s):

Sadaf

Salehkalaibar

(University of Tehran)
Vincent

Y. F.

Tan

(National University of Singapore)
Abstract:

In this paper, we consider sequential testing over a single-sensor, a single-decision center setup. At each time instant t, the sensor gets k samples (k>0) and describes the observed sequence until time t to the decision center over a zero-rate noiseless link. The decision center sends a single bit of feedback to the sensor to request for more samples for compression/testing or to stop the transmission. We have characterized the optimal exponent of type-II error probability under the constraint that type-I error probability does not exceed a given threshold \epsilon\in (0,1) and also when the expectation of the number of requests from decision center is smaller than n which tends to infinity. Interestingly, the optimal exponent coincides with that for fixed-length hypothesis testing with zero-rate communication constraints.

11:38 pm - 11:46 pm (JST)

Author(s):

Mustapha

Hamad

(Télécom Paris)
Michele

A

Wigger

(Telecom Paris)
Mireille

Sarkiss

(Telecom SudParis)
Abstract:

Cascaded binary hypothesis testing is studied in this paper with two decision centers at the relay and the receiver. All terminals have their own observations, where we assume that the observations at the transmitter, the relay, and the receiver form a Markov chain in this order. The communication occurs over two hops, from the transmitter to the relay and from the relay to the receiver. Expected rate constraints are imposed on both communication links. In this work, we characterize the optimal type-II error exponents at the two decision centers under constraints on the allowed type-I error probabilities. Our recent work characterized the optimal type-II error exponents in the special case when the two decision centers have same type-I error constraints and provided an achievability scheme for the general setup. To obtain the exact characterization for the general case, in this paper we provide a new converse proof as well as a new matching achievability scheme. Our results indicate that under unequal type-I error constraints at the relay and the receiver, a tradeoff arises between the maximum type-II error probabilities at these two terminals. Previous results showed that such a tradeoff does not exist under equal type-I error constraints or under general type-I error constraints when a maximum rate constraint is imposed on the communication links.

11:46 pm - 11:54 pm (JST)

Author(s):

Xiangxiang

Xu

(Tsinghua-Berkeley Shenzhen Institute, China)
Shao-Lun

Huang

(Tsinghua-Berkeley Shenzhen Institute)
Abstract:

In this paper, we consider the distributed hypothesis testing (DHT) problem where two nodes are constrained to transmit constant bits to a central decoder. In such cases, we show that in order to achieve the optimal error exponents, it suffices to consider the empirical distributions of observed data sequences and encode them to the transmission bits. With such a coding strategy, we develop a geometric approach in the distribution spaces to show the optimal achievable error exponents and coding scheme for the following cases: (i) both nodes can transmit log 2 3 bits; (ii) one of the nodes can transmit 1 bit, and the other node is not constrained; (iii) the joint distribution of the nodes are conditionally independent given one hypothesis. Our approach essentially reveals new potentials for characterizing the precise error exponents for DHT with general communication constraints.

Information Theory and Biology
Oct 19, 2021

11:30 pm - 11:38 pm (JST)

Author(s):

Yonatan

Yehezkeally

(Technical University of Munich)
Sagi

Marcovich

(Technion - Israel Institute of Technology)
Eitan

Yaakobi

(Technion)
Abstract:

The problem of reconstruction of strings based upon their substrings spectrum has received significant attention recently due to its applicability to DNA applications in storage and sequencing. In contrast to previous works, we consider in this paper the setup of this problem where multiple strings are reconstructed together. Given a multiset S of strings, all their substrings of some fixed length \ell, defined as the \ell-profile of S, are received and the goal is to reconstruct all strings in the multiset S. A multi-strand \ell-reconstruction code is a set of multisets such that every multiset S can be reconstructed from its \ell-profile. Given the number of strings k and their length n, we first find a lower bound on the value of \ell to have multi-strand \ell-reconstruction codes with asymptotic rate 1. We then present two constructions of such codes and show that their rates approach 1 for values of \ell that asymptotically behave like the lower bound to have this asymptotic rate.

11:38 pm - 11:46 pm (JST)

Author(s):

Roy

Shafir

(Technion - Israel Institute of Technology)
Omer

Sabary

(University of California, San Diego)
Leon

Anavy

(IDC Herzeliya)
Eitan

Yaakobi

(Technion)
Zoar

Yakhini

(IDC)
Abstract:

Synthetic DNA is an attractive alternative for data storage media due to its high information density, low energy usage, and exceptional robustness. Enzymatic DNA synthesis was recently introduced to allow cost effective synthesis of longer DNA molecules for data storage. This method is characterized by stutter errors which are sticky insertions so that every base in the designed sequence may be synthesized more than once. In this work, we study the problem of reconstructing the original sequence from a set of noisy reads originating from the stuttering enzymatic synthesis. We present different reconstruction algorithms and analyze their expected success probability and error rate for three different scenarios that depend on the information which is known about the stutter errors. We evaluate algorithmic performance analytically as well as by using simulations. We are especially interested in characterizing the performance as a function of the read depth. Our findings can be used to evaluate the trade-offs between synthesis quality indicators and the sequencing depth required for reconstruction with high probability. In principle, the probability of reconstruction failure exponentially decays with the sequencing depth, as demonstrated in the study. We also analyze the use of error-correcting codes to improve the error performance.

11:46 pm - 11:54 pm (JST)

Author(s):

Yuanyuan

Tang

(The University of Virginia)
Farzad

Farnoud

(University of Virginia)
Abstract:

DNA is considered a promising alternative to traditional storage media because of advantages such as high data density, longevity, and ease of generating copies. One of the major drawbacks of DNA data storage however is that DNA synthesis is costly and resource intensive. A newly proposed enzymatic method has the potential to decrease the cost of synthesis but has the disadvantage that the number of times a base is repeated cannot be precisely controlled. The method is also prone to deletion of runs. Existing encoding approaches for this synthesis method either have a low rate, specifically, ..\le \log_2 3.. per run, or cannot protect against deletion errors. The current paper proposes a new error-correcting code and a synchronization algorithm that can combat deletions and achieve a code rate higher than ..\log_2 3.. bits per unit time.

Information Measures and Statistics
Oct 20, 2021

9:00 pm - 9:08 pm (JST)

Author(s):

Koshi

Shimada

(Waseda University)
Shota

Saito

(Gunma University)
Toshiyasu

Matsushima

(Waseda University)
Abstract:

The context tree source is a source model in which the occurrence probability of symbols is determined from a finite past sequence, and is a broader class of sources that includes i.i.d. and Markov sources. This paper proposes a source model such that its subsequence is generated from a different context tree model. The Bayes code for such sources requires weighting of the posterior probability distributions for the change patterns of the context tree source and all possible context tree models. Therefore, the challenge is how to reduce this exponential order computational complexity. In this paper, we assume a special class of prior probability distribution of change patterns and context tree models, and propose an efficient Bayes coding algorithm whose computational complexity is the polynomial order.

9:08 pm - 9:16 pm (JST)

Author(s):

Shuchan

Wang

(KTH Royal Institute of Technology)
Photios

A.

Stavrou

(KTH Royal Institute of Technology)
Mikael

Skoglund

(KTH Royal Institute of Technology)
Abstract:

In this paper, we study the connection between entropic optimal transport and entropy power inequality (EPI). First, we prove an HWI-type inequality making use of the infinitesimal displacement convexity of optimal transport map. Second, we derive two Talagrand-type inequalities using the saturation of EPI that corresponds to a numerical term in our expression. We evaluate for a wide variety of distributions this term whereas for Gaussian and i.i.d. Cauchy distributions this term is found in explicit form. We show that our results extend previous results of Gaussian Talagrand inequality for Sinkhorn distance to the strongly log-concave case.

9:16 pm - 9:24 pm (JST)

Author(s):

Cheuk Ting

Li

(The Chinese University of Hong Kong)
Abstract:

We establish the undecidability of conditional affine information inequalities, the undecidability of the conditional independence implication problem with a constraint that one random variable is binary, and the undecidability of the problem of deciding whether the intersection of the entropic region and a given affine subspace is empty. This is a step towards the conjecture on the undecidability of conditional independence implication. The undecidability is proved via a reduction from the periodic tiling problem (a variant of the domino problem).

LDPC Codes
Oct 20, 2021

9:00 pm - 9:08 pm (JST)

Author(s):

Boris

D.

Kudryashov

(St. Petersburg University of Information Technologies, Mechanics and Optics)
Irina

Bocharova

(St. Petersburg University of Information Technologies, Mechanics and Optics)
Evgenii P.

Ovsyannikov

(State University of Aerospace Instrumentation)
Vitaly

Skachek

(University of Tartu)
Abstract:

A finite-length random coding bound on the maximum-likelihood decoding error probability for an ensemble of irregular NB LDPC codes with QAM signaling for specific code symbol-to-signal mappings is derived. Simulation results for the frame error rate (FER) performance of belief-propagation decoding for the optimized NB quasi-cyclic (QC)-LDPC codes used in various coded modulation schemes are presented. Comparison with the same performance of the optimized binary QC-LDPC block codes in the WiFi and 5G standards, as well as with the new bound is performed.

9:08 pm - 9:16 pm (JST)

Author(s):

Mgeni Makambi

Mashauri

(Lund University)
Alexandre

Graell i Amat

(Chalmers University of Technology)
Michael

Lentmaier

(Lund University)
Abstract:

In this paper, we derive the exact input/output transfer functions of the optimal a-posteriori probability channel detector for a general ISI channel with erasures. Considering three channel impulse responses of different memory as an example, we compute the BP and MAP thresholds for regular spatially coupled LDPC codes with joint iterative detection and decoding. When we compare the results with the thresholds of ISI channels with Gaussian noise we observe an apparent inconsistency, i.e., a channel which performs better with erasures performs worse with AWGN. We show that this anomaly can be resolved by looking at the thresholds from an entropy perspective. We finally show that with spatial coupling we can achieve the symmetric information rates of different ISI channels using the same code.

9:16 pm - 9:24 pm (JST)

Author(s):

Debarnab

Mitra

(University of California, Los Angeles)
Lev

Tauz

(University of California, Los Angeles)
Lara

Dolecek

(UCLA)
Abstract:

A popular method of improving the throughput of blockchain systems is by running smaller side blockchains that push the hashes of their blocks onto a trusted blockchain. Side blockchains are vulnerable to stalling attacks where a side blockchain node pushes the hash of a block to the trusted blockchain but makes the block unavailable to other side blockchain nodes. Recently, Sheng et al. proposed a data availability oracle based on LDPC codes and a data dispersal protocol as a solution to the above problem. While showing improvements, the codes and dispersal protocol were designed disjointly which may not be optimal in terms of the communication cost associated with the oracle. In this paper, we provide a tailored dispersal protocol and specialized LDPC code construction based on the Progressive Edge Growth (PEG) algorithm, called the dispersal-efficient PEG (DE-PEG) algorithm, aimed to reduce the communication cost associated with the new dispersal protocol. Our new code construction reduces the communication cost and, additionally, is less restrictive in terms of system design.

Information Security I
Oct 20, 2021

9:00 pm - 9:08 pm (JST)

Author(s):

Alireza

Poostindouz

(University of Calgary)
Reihaneh

Safavi-Naini

(University of Calgary)
Abstract:

In secret key agreement (SKA) in multiterminal channel model, terminals are connected by a noisy discrete memoryless channel (DMC) with multiple input and multiple outputs. Terminals can use the DMC to obtain correlated randomness, and communicate over a noiseless public channel to establish a shared secret key among a designated subset of terminals. We focus on a special class of multiterminal channel models, called wiretapped Polytree-PIN, in which the noisy channel consists of a set of independent point-to-point channels whose underlying undirected connectivity graph forms a tree. We consider a wiretap setting, where the output of each point-to-point channel is partially leaked to a passive wiretapper adversary, Eve, through a second independent noisy channel. A secure SKA protocol generates a group secret key such that Eve has no information about it. In this paper, we derive the wiretap secret key capacity, which is the largest achievable secret key rate, of the wiretapped Polytree-PIN model. Our result also implies the key capacity of the non-wiretapped Polytree-PIN model, that is the case when there is no leakage from point-to-point channels to Eve.

9:08 pm - 9:16 pm (JST)

Author(s):

Hiroki

Koga

(University of Tsukuba)
Abstract:

Digital fingerprinting codes are used to protect copyrighted contents from unauthorized redistribution. In this paper we focus on a digital fingerprinting code that can identify both of two malicious users and investigate coding theorems. We give a new definition of an identifier of the malicious users which enables us to give an explicit formula of the joint capacity, the supremum achievable rate of the number of users. Two coding theorems are given under the two kinds of setups depending on the knowledge of an attack model of the malicious users.

9:16 pm - 9:24 pm (JST)

Author(s):

Sara

Saeidian

(KTH Royal Institute of Technology)
Giulia

Cervia

(IMT Lille Douai)
Tobias

J.

Oechtering

(KTH Royal Institute of Technology)
Mikael

Skoglund

(KTH Royal Institute of Technology)
Abstract:

Most methods for publishing data with privacy guarantees introduce randomness into datasets which reduces the utility of the published data. In this paper, we study the privacy-utility tradeoff by taking maximal leakage as the privacy measure and the expected Hamming distortion as the utility measure. We study three different but related problems. First, we assume that the data-generating distribution (i.e., the prior) is known, and we find the optimal privacy mechanism that achieves the smallest distortion subject to a constraint on maximal leakage. Then, we assume that the prior belongs to some set of distributions, and we formulate a min-max problem for finding the smallest distortion achievable for the worst-case prior in the set, subject to a maximal leakage constraint. Lastly, we define a partial order on privacy mechanisms based on the largest distortion they generate. Our results show that when the prior distribution is known, the optimal privacy mechanism fully discloses symbols with the largest prior probabilities, and suppresses symbols with the smallest prior probabilities. Furthermore, we show that sets of priors that contain more uniform distributions lead to larger distortion, while privacy mechanisms that distribute the privacy budget more uniformly over the symbols create smaller worst-case distortion.

Machine Learning II
Oct 20, 2021

9:30 pm - 9:38 pm (JST)

Author(s):

Mert Bora

Dogan

(EPFL)
Michael

Gastpar

(EPFL)
Abstract:

The expected excess risk of a learning algorithm is the average suboptimality of using the learning algorithm, relative to the optimal hypothesis in the hypothesis class. In this work, we lower bound the expected excess risk of a learning algorithm using the mutual information between the input and the noisy output of the learning algorithm. The setting we consider is, where the hypothesis class is the set of real numbers and the true risk function has a local strong convexity property. Our main results also lead to asymptotic lower bounds on the expected excess risk, which do not require the knowledge of the local strong convexity constants of the true risk function.

9:38 pm - 9:46 pm (JST)

Author(s):

Eeshan

Modak

(Tata Institute of Fundamental Research)
Himanshu

Asnani

(Tata Institute of Fundamental Research, Mumbai & University of Washington, Seattle)
Vinod

M

Prabhakaran

(Tata Institute of Fundamental Research)
Abstract:

Generalization error captures the degree to which the output of a learning algorithm overfits the training data. We obtain a family of bounds which generalize the bounds developed by Xu & Raginsky (2017) and Bu, Zou and Veeravalli (2019), under certain assumptions. Our bounds are based on the Rényi analogue of the Donsker-Varadhan representation of Kullback-Leibler divergence. We also obtain bounds on the probability of generalization error which recover the bounds of Esposito, Gastpar and Issa (2020). We also give a multiplicative lower bound on the expected true loss for a 0-1 loss function.

9:46 pm - 9:54 pm (JST)

Author(s):

Ayşe

Ünsal

(EURECOM)
Melek

Önen

(EURECOM)
Abstract:

This paper studies the statistical characterization of detecting an adversary who wants to harm some computation such as machine learning models or aggregation by altering the output of a differentially private mechanism in addition to discovering some information about the underlying dataset. An adversary who is able to modify the published information from a differentially private mechanism aims to maximize the possible damage to the system while remaining undetected. We present a trade-off between the privacy parameter of the system, the sensitivity and the attacker's advantage (the bias) through determining the threshold for the best critical region of the hypothesis testing problem for deciding whether or not the adversary's attack is detected. Such trade-offs are provided for Laplace mechanisms using one-sided and two-sided hypothesis tests. Corresponding error probabilities are analytically derived and ROC curves are presented for various levels of the sensitivity, the absolute mean of the attack and the privacy parameter. Subsequently, we provide an interval for the bias induced by the adversary so that the defender detects the attack. Finally, we adapt the Kullback-Leibler differential privacy to adversarial classification.

Decoding
Oct 20, 2021

9:30 pm - 9:38 pm (JST)

Author(s):

Liudmila

Karakchieva

(ITMO University)
Peter

Trifonov

(ITMO University)
Abstract:

A novel SISO decoding algorithm for linear block codes is presented. This algorithm is based on the recursive trellises and performs two passes over the recursion tree. Probability-domain implementation and its LogMax approximation are considered. Numeric results show that proposed method has lower complexity compared to the other known recursive algorithms and the classical BCJR algorithm.

9:38 pm - 9:46 pm (JST)

Author(s):

Peihong

Yuan

(Technical University of Munich)
Mustafa

Cemil

Coşkun

(Technische Universität München)
Abstract:

A complexity-adaptive tree search algorithm is proposed for ..\boldsymbol{G}_N..-coset codes that implements maximum-likelihood (ML) decoding by using a successive decoding schedule. The average complexity is close to that of the successive cancellation (SC) decoding for practical error rates when applied to polar codes and short Reed-Muller (RM) codes, e.g., block lengths up to ..N=128... By modifying the algorithm to limit the worst-case complexity, one obtains a near-ML decoder for longer RM codes and their subcodes. Unlike other bit-flip decoders, no outer code is needed to terminate decoding. The algorithm can thus be applied to modified ..\boldsymbol{G}_N..-coset code constructions with dynamic frozen bits. One advantage over sequential decoders is that there is no need to optimize a separate parameter.

9:46 pm - 9:54 pm (JST)

Author(s):

Warangrat

Wiriya

(Japan Advanced Institute of Science and Technology)
Brian

Michael

Kurkoski

(Japan Advanced Institute of Science and Technology (JAIST))
Abstract:

This paper proposes a low-complexity decoding algorithm for complex low-density lattice codes (CLDLC). The key is a method to approximate an infinite complex Gaussian mixture that occurs at the variable node of the belief propagation (BP) decoder. We define the reliability of check-to-variable messages and a threshold function to determine the number of complex Gaussian functions to use in the approximation. This allows the number of Gaussians in the approximation to be adaptively selected depending upon its reliability. By using the minimum number of Gaussians needed for an accurate approximation, the complexity of the decoder can be significantly reduced. The reliability is based on a likelihood function, and we form an upper bound on the Kullback-Leibler (KL) divergence to find the threshold function via linear regression. The approximation based on reliability of each message can reduce the complexity to O(n · t · 1.35 d−1 ) at high volume-to-noise ratio (VNR), where n is the lattice dimension, d is the degree of the inverse generator matrix, and t is the number of iterations. This algorithm provides higher performance and lower complexity compared to previously proposed approximation algorithms. and provides higher performance and lower complexity compared to previously proposed approximation algorithms.

Information Security II
Oct 20, 2021

9:30 pm - 9:38 pm (JST)

Author(s):

Yucheng

Liu

(The University of Newcastle, Australia)
Lawrence

Ong

(The University of Newcastle)
Phee Lep

Yeoh

(University of Sydney)
Parastoo

Sadeghi

(University of New South Wales)
Joerg

Kliewer

(New Jersey Institute of Technology)
Sarah

J

Johnson

(University of Newcastle)
Abstract:

We study the information leakage to a guessing adversary in index coding with a general message distribution. Under both vanishing-error and zero-error decoding assumptions, we develop lower and upper bounds on the optimal leakage rate, which are based on the broadcast rate of the subproblem induced by the set of messages the adversary tries to guess. When the messages are independent and uniformly distributed, the lower and upper bounds match, establishing an equivalence between the two rates.

9:38 pm - 9:46 pm (JST)

Author(s):

Yucheng

Liu

(The University of Newcastle, Australia)
Lawrence

Ong

(The University of Newcastle)
Parastoo

Sadeghi

(University of New South Wales)
Neda

Aboutorab

(University of New South Wales)
Arman

Sharififar

(University of New South Wales)
Abstract:

In this work, we study the secure index coding problem where there are security constraints on both legitimate receivers and eavesdroppers. We develop two performance bounds (i.e., converse results) on the symmetric secure capacity. The first one is an extended version of the basic acyclic chain bound (Liu and Sadeghi, 2019) that takes security constraints into account. The second converse result is a novel information-theoretic lower bound on the symmetric secure capacity, which is interesting as all the existing converse results in the literature for secure index coding give upper bounds on the capacity.

9:46 pm - 9:54 pm (JST)

Author(s):

Abdalla

Ibrahim

(Technische Universität München)
Roberto

Ferrara

(Technische Universität München & Institute for Communications Engineering)
Christian

Deppe

(Technical University of Munich)
Abstract:

We study the problem of identification over a DMC wiretap channel under effective secrecy. In identification, due to the fact that single messages are compared to each other, all conditions are inherently semantic, and thus we are forced to consider semantic effective secrecy. We show that even considering effective secrecy "comes for free" by giving an achievability theorem for stealth identification. We use two concatenated transmission codes, the first one is a resolvability transmission code. The second code is an effective-secrecy transmission code. An achievable rate is derived for the problem.

Sparse Recovery
Oct 20, 2021

11:00 pm - 11:08 pm (JST)

Author(s):

Hang

Zhang

(Georgia Institute of Technology)
Afshin

Abdi

(Qualcomm)
Faramarz

Fekri

(Georgia Institute of Technology)
Abstract:

This paper proposes a general framework to design a sparse sensing matrix A\in R^{m\times n}, in a linear measurement system y = \Ax^{\natural} + w, where y \in R^n, x^{\natural}\in R^n, and w denote the measurements, the signal with certain structures, and the measurement noise, respectively. By viewing the signal reconstruction from the measurements as a message passing algorithm over a graphical model, we leverage tools from coding theory in the design of low density parity check codes, namely the density evolution, and provide a framework for the design of matrix A. Particularly, compared to the previous methods, our proposed framework enjoys the following desirable properties: (i) Universality: the design supports both regular reconstruction and preferential reconstruction, and incorporates them in a single framework; (ii) Flexibility: the framework can easily adapt the design of A to a signal x^{\natural} with different underlying structures. As an illustration, we consider the L1 regularizer, which correspond to Lasso, for both the regular reconstruction and preferential reconstruction scheme. Noteworthy, our framework can reproduce the classical result of Lasso, i.e., m\geq c_0 k\log(n/k) (the regular reconstruction) with regular design after proper distribution approximation, where c_0 > 0 is some fixed constant. We also provide numerical experiments to confirm the analytical results and demonstrate the superiority of our framework whenever a preferential treatment of a sub-block of vector x^{\natural} is required.

11:08 pm - 11:16 pm (JST)

Author(s):

Zhaoqiang

Liu

(National University of Singapore)
Subhroshekhar

Ghosh

(National University of Singapore)
Jonathan

Scarlett

(National University of Singapore)
Abstract:

In 1-bit compressive sensing, each measurement is quantized to a single bit, namely the sign of a linear function of an unknown vector, and the goal is to accurately recover the vector. While it is most popular to assume a standard Gaussian sensing matrix for 1-bit compressive sensing, using structured sensing matrices such as partial Gaussian circulant matrices is of significant practical importance due to their faster matrix operations. In this paper, we provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing with partial Gaussian circulant matrices (with random column sign flips) under a generative prior, where the signal to estimate is assumed to belong to the range of a Lipschitz continuous generative model with bounded inputs. Under suitable assumptions, we match guarantees that were previously only known to hold for i.i.d.~Gaussian matrices requiring significantly more computation.

11:16 pm - 11:24 pm (JST)

Author(s):

Pouria

Saidi

(University of Central Florida)
George

Atia

(University of Central Florida)
Abstract:

Periodic signals admit sparse representations in nested periodic dictionaries (NPDs). While sparse recovery algorithms rooted in the theory of compressive sensing can successfully recover their underlying periods, existing recovery conditions derived for random dictionaries are of limited use in this context as they fail to explain the achievability results of said algorithms. In addition, provable achievability guarantees specific to NPDs have been heretofore lacking. In this paper, we derive exact recovery conditions for sparse periodic signals by leveraging prior information about the structure of NPDs. As instances of such dictionaries, we investigate the achievability conditions for the Farey and the Ramanujan Periodicity Transform dictionaries. Our numerical results demonstrate that the newly derived conditions can provide guarantees for exact recovery with the Farey dictionary, and in turn for exact period estimation, for large enough data lengths.

11:24 pm - 11:32 pm (JST)

Author(s):

Wencong

Li

(Japan Advanced Institute of Science and Technology)
Lei

Liu

(Japan Advanced Institute of Science and Technology)
Brian

Michael

Kurkoski

(Japan Advanced Institute of Science and Technology (JAIST))
Abstract:

Recently, it was found that clipping can significantly improve the section error rate (SER) performance of sparse regression (SR) codes if an optimal clipping threshold is chosen. In this paper, we propose irregularly clipped SR codes, where multiple clipping thresholds are applied to symbols according to a distribution, to further improve the SER performance of SR codes. Orthogonal approximate message passing (OAMP) algorithm is used for decoding. Using state evolution, the distribution of irregular clipping thresholds is optimized to minimize the SER of OAMP decoding. As a result, optimized irregularly clipped SR codes achieve a better tradeoff between clipping distortion and noise distortion than regularly clipped SR codes. Numerical results demonstrate that irregularly clipped SR codes achieve 0.4 dB gain in signal-to-noise-ratio (SNR) over regularly clipped SR codes at code length 2.5 x 10^4 and SER = 10^-5. We further show that irregularly clipped SR codes are robust over a wide range of code rates.

Coding Theory and Practice
Oct 20, 2021

11:00 pm - 11:08 pm (JST)

Author(s):

Hanxu

Hou

(Dongguan University of Technology)
Patrick Pak-Ching

Lee

(The Chinese University of Hong Kong)
Abstract:

STAR codes are well-known binary Maximum Distance Separable (MDS) array codes with triple fault tolerance and low encoding/decoding complexity, yet the update complexity of STAR codes is sub-optimal. We propose STAR+ codes, which extend STAR codes to achieve asymptotically optimal update complexity. We show that STAR+ codes are the generalized version of STAR codes with triple fault tolerance, and additionally have strictly less complexity in encoding, decoding, and updates than STAR codes for most parameters.

11:08 pm - 11:16 pm (JST)

Author(s):

Hiroyoshi

Morita

(The University of Electro-Communications)
Masaya

Fujisawa

(Tokyo University of Science)
Shojiro

Sakata

(University of Electro-Communications)
Abstract:

We construct linear codes over odd prime fields for correcting two-dimensional (2-D) Lee-errors on the hexagonal signal constellations. They are obtained by puncturing and enlarging either RS codes or BCH codes. We introduce 2-D Lee-weight on the hexagonal constellations in the same way as the method presented by the first author in ISIT'19, and propose an effective method for correcting Lee-errors of weight greater than or equal to 1. The concept of value-locator of an error, which was introduced implicitly by K. Nakamura in the late 1970s and early 1980s and inherited to the ISIT'19 paper, is a key for decoding Lee-error-correcting codes. Our method is based on the Buchberger algorithm for finding Gröbner bases of ideals in the multivariate polynomial ring. A result of simulations shows that our method works well for correcting Lee-errors of small weight.

11:16 pm - 11:24 pm (JST)

Author(s):

Anina

Gruica

(Eindhoven University of Technology)
Alberto

Ravagnani

(University of Toronto)
Abstract:

We consider the problem of describing the typical (possibly) non-linear code of minimum distance bounded from below over a large alphabet. We concentrate on block codes with the Hamming metric and on subspace codes with the injection metric. In sharp contrast with the behavior of linear block codes, we show that the typical non-linear code in the Hamming metric of cardinality \(q^{n-d+1}\) is far from having minimum distance \(d\), i.e., from being MDS. We also give more precise results about the asymptotic proportion of block codes with good distance properties within the set of codes having a certain cardinality. We then establish the analogous results for subspace codes with the injection metric, showing also an application to the theory of partial spreads in finite geometry.

Information Security III
Oct 20, 2021

11:00 pm - 11:08 pm (JST)

Author(s):

Yi

Liu

(Télécom Paris & Institut Polytechnique de Paris)
Wei

Cheng

(Télécom Paris & Institut Polytechnique de Paris)
Sylvain

Guilley

(Telecom ParisTech & Secure-IC)
Olivier

Rioul

(Telecom Paris, Institut Polytechnique de Paris & Ecole Polytechnique)
Abstract:

A conditional version of Sibson's α-information is defined using a simple closed-form "log-expectation" expression, which satisfies important properties such as consistency, uniform expansion, and data processing inequalities. This definition is compared to previous ones, which in contrast do not satisfy all of these properties. Based on our proposal and on a generalized Fano inequality, we extend the case α=1 of previous works to obtain sharp universal upper bounds for the probability of success of any type side-channel attack, particularly when α = 2.

11:08 pm - 11:16 pm (JST)

Author(s):

Maki

Yoshida

(National Institute of Information and Communications Technology)
Abstract:

A secret-sharing scheme is $d$-multiplicative if it allows the players to multiply $d$ (rather than two) shared secrets (without recovering them) by {\em locally} converting their shares into an additive sharing of the product. In this work, the $d$-multiplicative secret-sharing (MSS) scheme is extended to a hybrid MSS (HMSS), which is mainly designed for $d$ secrets shared against different access structures. A necessary and sufficient condition for $n$-player $d$-HMSS schemes to exist is presented. The sufficiency is constructively proven based on the replication-based secret-sharing scheme. The necessity for any general case is reduced to the impossibility of a minimum case. The results holds for arbitrary (possibly inefficient or even nonlinear) secret-sharing schemes.

11:16 pm - 11:24 pm (JST)

Author(s):

Hamid

Ghourchian

(KTH Royal Institute of Technology)
Photios

A.

Stavrou

(KTH Royal Institute of Technology)
Tobias

J.

Oechtering

(KTH Royal Institute of Technology)
Mikael

Skoglund

(KTH Royal Institute of Technology)
Abstract:

We study the problem of rate-distortion-equivocation with side-information only available at the decoder when an independent private random key is shared between the sender and the receiver. The sender compresses the sequence, and the receiver reconstructs it such that the average distortion between the source and the output is limited. The equivocation is measured at an eavesdropper that intercepts the source encoded message, utilizing side-information correlated with the source and the side-information at the decoder. We have derived the entire achievable rate-distortion-equivocation region for this problem.

Coding Theory
Oct 20, 2021

11:40 pm - 11:48 pm (JST)

Author(s):

Daniella

Bar-Lev

(Technion)
Omer

Sabary

(University of California, San Diego)
Yotam

Gershon

(Technion - Israel Institute of Technology)
Eitan

Yaakobi

(Technion)
Abstract:

This paper studies the intersections of insertion and deletion balls. The t-insertion, t-deletion ball of a sequence x is the set of all sequences received by t insertions, deletions to x, respectively. While the intersection of either deletion balls or insertion balls has been rigorously studied before, the intersection of an insertion ball and a deletion ball has not been addressed so far. We find the maximum intersection size of any two insertion and deletion balls in the binary case. For the special case of one-insertion and one-deletion balls we find the intersection size for all pair of sequences. Then, we derive the largest and average values of this intersection size. Lastly, we present an algorithm that efficiently computes the intersection of any t1-insertion ball and t2-deletion ball.

11:48 pm - 11:56 pm (JST)

Author(s):

Mladen

Kovačević

(University of Novi Sad)
Dejan

Vukobratović

(University of Novi Sad)
Abstract:

We study properties of binary runlength-limited sequences with additional constraints on their weight and/or the number of runs of identical symbols they contain. An algebraic and a probabilistic (entropic) characterization of the exponential growth rate of the number of such sequences, i.e., their information capacity, are obtained, and properties of the capacity as a function of its parameters are stated. The second-order term in the asymptotic expansion of the rate of these sequences is also given, and the typical values of the relevant quantities are derived. Several applications of the results are illustrated, including bounds on codes for the run-preserving insertion-deletion channel, a sphere-packing bound for channels with sparse error patterns, and the asymptotics of constant-weight sub-block constrained sequences.

11:56 am - 12:04 am (JST)

Author(s):

Patrick

Solé

(Telecom Paristech)
Yi

Liu

(Télécom Paris & Institut Polytechnique de Paris)
Wei

Cheng

(Télécom Paris & Institut Polytechnique de Paris)
Sylvain

Guilley

(Telecom ParisTech & Secure-IC)
Olivier

Rioul

(Telecom Paris, Institut Polytechnique de Paris & Ecole Polytechnique)
Abstract:

We use linear programming (LP) to derive upper and lower bounds on the ``kissing number'' Ad of any q-ary linear code C with distance distribution frequencies A_i, in terms of the given parameters [n, k, d]. In particular, a polynomial method gives explicit analytic bounds in a certain range of parameters, which are sharp for some low-rate codes like the first-order Reed-Muller codes. The general LP bounds are more suited to numerical estimates. Besides the classical estimation of the probability of decoding error and of undetected error, we outline recent applications in hardware protection against side-channel attacks using code-based masking countermeasures, where the protection is all the more efficient as the kissing number is low.

Shannon Theory I
Oct 21, 2021

9:00 pm - 9:08 pm (JST)

Author(s):

Alex

Dytso

(New Jersey Institute of Technology)
Luca

Barletta

(Politecnico di Milano)
Shlomo (Shitz)

Shamai

(The Technion)
Abstract:

This work considers a Poisson noise channel with an amplitude constraint. It is well-known that the capacity-achieving input distribution for this channel is discrete with finitely many points. We sharpen this result by introducing upper and lower bounds on the number of mass points. In particular, the upper bound of order ..A \log^2(A).. and lower bound of order ..\sqrt{A}.. are established where ..A.. is the constraint on the input amplitude. In addition, along the way, we show several other properties of the capacity and capacity-achieving distribution. For example, it is shown that the capacity is equal to .. - \log P_{Y^\star}(0).. where ..P_{Y^\star}.. is the optimal output distribution. Moreover, an upper bound on the values of the probability masses of the capacity-achieving distribution and a lower bound on the probability of the largest mass point are established.

9:08 pm - 9:16 pm (JST)

Author(s):

Giulia

Cervia

(IMT Lille Douai)
Tobias

J.

Oechtering

(KTH Royal Institute of Technology)
Mikael

Skoglund

(KTH Royal Institute of Technology)
Abstract:

This paper investigates the problem of synthesizing joint distributions in the finite-length regime. For a fixed block-length n and an upper bound on the distribution approximation epsilon, we prove a capacity result for fixed-length strong coordination. It is shown analytically that the rate conditions for the fixed-length regime are lower-bounded by the mutual information that appears in the asymptotical condition plus Q^-1 (epsilon) sqrt(V/n), where V is the channel dispersion, and Q^-1 is the inverse of the Gaussian cumulative distribution function.

9:16 pm - 9:24 pm (JST)

Author(s):

Michail

Mylonakis

(KTH Royal Institute of Technology)
Photios

A.

Stavrou

(KTH Royal Institute of Technology)
Mikael

Skoglund

(KTH Royal Institute of Technology)
Abstract:

We generalize the problem of controlling the interference created to an external observer while communicating over a Discrete Memoryless Channel (DMC) which was studied in [1]. In particular, we consider the scenario where the transmission is established over a compound DMC channel with unknown state at both the encoder and the decoder. Depending on the exact state s of the channel, we ask for a different level of average precision Δs on the establishment of the interference coordination with the external observer. For this set-up, we fully characterize the capacity region.

MIMO
Oct 21, 2021

9:00 pm - 9:08 pm (JST)

Author(s):

Rami

Ezzine

(Technical University of Munich)
Moritz

Wiese

(Technical University of Munich)
Christian

Deppe

(Technical University of Munich)
Holger

Boche

(Technical University Munich)
Abstract:

We investigate the problem of common randomness (CR) generation from discrete correlated sources aided by one-way communication over single-user multiple-input multiple-output (MIMO) slow fading channels with additive white Gaussian noise (AWGN), arbitrary state distribution and with channel state information available at the receiver side (CSIR). We completely solve the problem by first characterizing the channel outage capacity of MIMO slow fading channels for arbitrary state distribution. For this purpose, we also provide an achievable rate for a specific compound MIMO Gaussian channel. Second, we define the outage CR capacity of the MIMO slow fading channel and establish a single-letter characterization of it using our result on its outage transmission capacity.

9:08 pm - 9:16 pm (JST)

Author(s):

Shuqin

Pang

(University of Science and Technology of China)
Wenyi

Zhang

(University of Science and Technology of China)
Abstract:

Information transmission over a multiple-input-multiple-output (MIMO) fading channel with imperfect channel state information (CSI) is investigated, under a new receiver architecture which combines the recently proposed generalized nearest neighbor decoding rule (GNNDR) and a successive procedure in the spirit of successive interference cancellation (SIC). Recognizing that the channel input-output relationship is a nonlinear mapping under imperfect CSI, the GNNDR is capable of extracting the information embedded in the joint observation of channel output and imperfect CSI more efficiently than the conventional linear scheme, as revealed by our achievable rate analysis via generalized mutual information (GMI). Numerical results indicate that the proposed scheme achieves performance close to the channel capacity with perfect CSI, and significantly outperforms the conventional pilot-assisted scheme, which first estimates the CSI and then uses the estimated CSI as the true one for coherent decoding.

9:16 pm - 9:24 pm (JST)

Author(s):

Khac-Hoang

Ngo

(Chalmers University of Technology)
Fan

Zhang

(University of Texas at Dallas)
Sheng

Yang

(CentraleSupélec)
Aria

Nosratinia

(University of Texas, Dallas)
Abstract:

In a multiple-input multiple-output (MIMO) broadcast channel (BC), the difference in spatial transmit correlation matrices of different users is called transmit correlation diversity. Recently, several works have extended this concept beyond its original scope, to include channels whose transmit correlation matrices have non-overlapping eigenspaces. In contrast to earlier analyses of overlapping eigenspaces that were mostly described in terms of degrees-of-freedom, this work presents achievable rate regions. These achievable regions are derived by rate-splitting, product superposition, or a combination thereof. Our rate expressions make explicit the contribution of the common parts and individual (non-overlapping) parts of the correlation eigenspaces toward the achievable rate region. As a by-product, a result of Hassibi and Hochwald on MIMO channel training is extended to channels with spatial correlation.

Quantum Information Theory I
Oct 21, 2021

9:00 pm - 9:08 pm (JST)

Author(s):

Yonglong

Li

(National University of Singapore)
Vincent

Y. F.

Tan

(National University of Singapore)
Marco

Tomamichel

(National University of Singapore)
Abstract:

We consider sequential hypothesis testing between two quantum states using adaptive and non-adaptive strategies. In this setting, samples of an unknown state are requested sequentially and a decision to either continue or to accept one of the two hypotheses is made after each test. Under the constraint that the number of samples is bounded, either in expectation or with high probability, we exhibit adaptive strategies that minimize both types of misidentification errors. Namely, we show that these errors decrease exponentially (in the stopping time) with decay rates given by the measured relative entropies between the two states. Moreover, if we allow joint measurements on multiple samples, the rates are increased to the respective quantum relative entropies. We also fully characterize the achievable error exponents for non-adaptive strategies and provide numerical evidence showing that adaptive measurements are necessary to achieve our bounds.

9:08 pm - 9:16 pm (JST)

Author(s):

Sayantan

Chakraborty

(Tata Institute of Fundamental Research)
Aditya

Nema

(Nagoya University)
Pranab

Sen

(Tata Institute of Fundamental Research)
Abstract:

We provide the first inner bounds for sending private classical information over a quantum multiple access channel. We do so by using three powerful information theoretic techniques: rate splitting, quantum simultaneous decoding for multiple access channels, and a novel smoothed distributed covering lemma for classical quantum channels. Our inner bounds are given in the one shot setting and accordingly the three techniques used are all very recent ones specifically designed to work in this setting. The last technique is new to this work and is our main technical advancement. For the asymptotic iid setting, our one shot inner bounds lead to the natural quantum analogue of the best classical inner bounds for this problem.

9:16 pm - 9:24 pm (JST)

Author(s):

Navneeth

Ramakrishnan

(Imperial College London)
Marco

Tomamichel

(National University of Singapore)
Mario

Berta

(Imperial College London)
Abstract:

Quantum state transfer involves two parties who use pre-shared entanglement and noiseless communication in order to transfer parts of a quantum state. In this work, we quantify the communication cost of one-shot state splitting in terms of the partially smoothed max-information. We then give an analysis of state splitting in the moderate deviation regime, where the error in the protocol goes sub-exponentially fast to zero as a function of the number of i.i.d. copies. The main technical tool we derive is a tight relation between the partially smoothed max-information and the hypothesis testing relative entropy, which allows us to obtain the expansion of the partially smoothed max-information for i.i.d. states in the moderate deviation regime. This then also establishes the moderate deviation analysis for other variants of state transfer such as state merging and source coding.

Shannon Theory II
Oct 21, 2021

9:30 pm - 9:38 pm (JST)

Author(s):

Arda

Atalik

(Bilkent University)
Alper

Kose

(Boğaziçi University)
Michael

Gastpar

(EPFL)
Abstract:

This paper considers an additive Gaussian noise channel with arbitrarily distributed finite variance input signals. It studies the differential entropy of the minimum mean-square error (MMSE) estimator and provides a new lower bound which connects the differential entropy of the input, output, and conditional mean. That is, the sum of differential entropies of the conditional mean and output is always greater than or equal to twice the input differential entropy. Various other properties such as upper bounds, asymptotics, Taylor series expansion, and connection to Fisher Information are obtained. An application of the lower bound in the remote-source coding problem is discussed, and extensions of the lower and upper bounds to the vector Gaussian channel are given.

9:38 pm - 9:46 pm (JST)

Author(s):

Amitalok

J.

Budkuley

(Indian Institute of Technology Kharagpur)
Pranav

Joshi

(Indian Institute of Technology Kharagpur)
Manideep

Mamindlapally

(Indian Institute of Technology Kharagpur)
Anuj

Kumar

Yadav

(Indian Institute of Technology Patna)
Abstract:

In this work, we study commitment over a class of channels called reverse elastic channels (RECs). In the commitment problem, two mutually distrustful parties, say Alice and Bob, seek to commit on a bit string available to Alice. The parties interact via a commitment protocol comprising two phases, viz., commit phase followed by reveal phase. Alice commits to a string, and transmits it to Bob securely in a manner Bob cannot learn it until Alice chooses to reveal it; at the time of reveal, however, Bob can successfully detect if Alice cheats. It is well known that noisy channels are a promising resource to realize information-theoretically secure commitment; however, oftentimes, channel behaviour may be poorly characterized thereby limiting the commitment throughput and/or degrading the security guarantees. Particularly problematic is a scenario where dishonest parties can actively alter the channel characteristics. RECs are an interesting class of such unreliable channels, where essentially only a dishonest committer Alice can meaningfully alter the channel; RECs have attracted active recent interest. Our principal contribution is the REC commitment capacity characterization for all parameters; this proves a recent related conjecture. Apart from presenting an achievable scheme, a key result in our work is a tight converse which analyses a specific cheating strategy by Alice. The significance of RECs stems from the fact that along with elastic channels (ECs), where only a dishonest receiver Bob can alter the channel, these two channel models represent special cases of the more widely studied unfair noisy channels (UNCs). Interestingly, for a given set of parameters, our result shows that the REC commitment capacity is no larger than that for the ECs. Furthermore, similar to the ECs, RECs offer non-trivial commitment throughput for all meaningful parameters; this is in stark contrast to UNCs where the throughput may possibly be zero.

9:46 pm - 9:54 pm (JST)

Author(s):

Holger

Boche

(Technical University Munich)
Christian

Deppe

(Technical University of Munich)
Abstract:

Zero-error capacity plays an important role in a whole range of operational tasks, in addition to the fact that it is necessary for practical applications. Due to the importance of zero-error capacity, it is necessary to investigate its algorithmic computability, as there has been no known closed formula for the zero-error capacity until now. We show that the zero-error capacity of noisy channels is not Banach-Mazur computable and therefore not Borel-Turing computable. This result also implies the uncomputability of the zero-error capacity for real-valued channel matrices characterized by means of an oracle machine. We also investigate the relationship between the zero-error capacity of discrete memoryless channels, the Shannon capacity of graphs, and Ahlswede's characterization of the zero-error-capacity of noisy channels with respect to the maximum error capacity of 0-1-arbitrarily varying channels. We will show that important questions regarding semi-decidability are equivalent for all three capacities. So far, the Borel-Turing computability of the Shannon capacity of graphs is completely open. This is why the coupling with semi-decidability is interesting. The authors conjecture that the zero-error capacity of a noisy channel may be computable with respect to some computation models other than the Turing machine, like neuromorphic-computers and specific types of quantum computers.

SWIPT & JSCC
Oct 21, 2021

9:30 pm - 9:38 pm (JST)

Author(s):

Sadaf Ul

Zuhra

(INRIA Sophia Antipolis)
Samir

M.

Perlaza

(INRIA)
Eitan

Altman

(INRIA)
Abstract:

In this paper, the fundamental limits on the rates at which information and energy can be simultaneously transmitted over an additive white Gaussian noise channel are studied under the following assumptions: (a) the channel is memoryless; (b) the number of channel input symbols (constellation size) and block length are finite; and (c) the decoding error probability (DEP) and the energy outage probability (EOP) are bounded away from zero. In particular, it is shown that the limits on the maximum information and energy transmission rates; and the minimum DEP and EOP, are essentially set by the type induced by the code used to perform the transmission. That is, the empirical frequency with which each channel input symbol appears in the codewords. Using this observation, guidelines for optimal constellation design for simultaneous energy and information transmission are presented.

9:38 pm - 9:46 pm (JST)

Author(s):

Nizar

Khalfet

(University of Cyprus)
Ioannis

Krikidis

(University of Cyprus)
Abstract:

In this paper, we study the fundamental limits of simultaneous information and power transfer over a Rayleigh fading channel in the presence of high-power amplifier (HPA) nonlinearity. In particular, a three-party communication system is considered, where a transmitter aims simultaneously conveying information to an information receiver and delivering energy to an energy harvester receiver. We study the information-energy capacity region and the associated input distribution under: i) average-power, peak-power (PP) constraints at the transmitter, b) HPA nonlinearity at the transmitter, and c) nonlinearity of the energy harvesting circuit at the energy receiver. By extending Smith's mathematical framework, we show that the optimal input distribution under those constraints is discrete with a finite number of mass points. Moreover, we derive a closed-form expression of the capacity-achieving distribution for the low PP regime, where there is no trade-off between information and energy transfer. Finally, we show that HPA significantly reduces the information energy capacity region.

9:46 pm - 9:54 pm (JST)

Author(s):

Omri

Lev

(Tel-Aviv University)
Anatoly

Khina

(Tel Aviv University)
Abstract:

We study the problem of transmitting a source sample with minimum distortion over an infinite-bandwidth additive white Gaussian noise channel under an energy constraint. To that end, we construct a joint source-channel coding scheme using analog pulse position modulation (PPM) and bound its quadratic distortion. We show that this scheme outperforms existing techniques since its quadratic distortion attains both the exponential and polynomial decay orders of Burnashev's outer bound.

9:54 pm - 10:02 pm (JST)

Author(s):

Naruki

Joki

(Wakayama University)
Shigeaki

Kuzuoka

(Wakayama University)
Abstract:

In this paper, a problem of joint source-channel coding for computing functions of outputs from correlated sources is studied. In particular, the system of computing two-input functions where one of two outputs is available at the decoder as full-side information is investigated. Our result reveals that if the sensitivity of functions introduced by Ahlswede and Csisz\'ar and the smoothness of sources introduced by Kuzuoka and Watanabe are satisfied, then the condition that the function is computable over the channel (i.e., the value of the function is correctly decoded) coincides with that for the identity function (i.e., reproducing the entire source outputs).

Quantum Information Theory II
Oct 21, 2021

9:30 pm - 9:38 pm (JST)

Author(s):

Uzi

Pereg

(Technical University of Munich)
Roberto

Ferrara

(Technische Universität München & Institute for Communications Engineering)
Matthieu

Bloch

(Georgia Institute of Technology)
Abstract:

Secret-sharing building blocks based on quantum broadcast communication are studied. The confidential capacity region of the pure-loss bosonic broadcast channel is determined with key assistance, under the assumption of the long-standing minimum output-entropy conjecture. If the main receiver has a transmissivity of ..\eta<\frac{1}{2}.., then confidentiality solely relies on the key-assisted encryption of the one-time pad. We also address conference key agreement for the distillation of two keys, a public key and a secret key. A regularized formula is derived for the key-agreement capacity region. In the pure-loss bosonic case, the key-agreement region is included within the capacity region of the corresponding broadcast channel with confidential messages. We then consider a network with layered secrecy, where three users with different security ranks communicate over the same broadcast network. We derive an achievable layered-secrecy region for a pure-loss bosonic channel that is formed by the concatenation of two beam splitters.

9:38 pm - 9:46 pm (JST)

Author(s):

Mark

M

Wilde

(Louisiana State University)
Abstract:

The distillable entanglement of a bipartite quantum state does not exceed its entanglement cost. This well known inequality can be understood as a second law of entanglement dynamics in the asymptotic regime of entanglement manipulation, excluding the possibility of perpetual entanglement extraction machines that generate boundless entanglement from a finite reserve. In this paper, I establish a refined second law of entanglement dynamics that holds for the non-asymptotic regime of entanglement manipulation.

9:46 pm - 9:54 pm (JST)

Author(s):

Minwoo

Bae

(University of Connecticut)
Walter

O

Krawec

(University of Connecticut)
Abstract:

Semi-source independent quantum random number generators (SI-QRNG) are cryptographic protocols which attempt to extract random strings from quantum sources where the source is under the control of an adversary (but with known dimension) while the measurement devices are fully characterized. This represents a middle-ground between fully-trusted and full-device independence, allowing for fast bit-generation rates with current-day technology, while also providing a strong security guarantee. In this paper we analyze a SI-QRNG protocol based on quantum walks and develop a proof of security. We derive a novel entropic uncertainty relation for this application which is necessary since standard relations actually fail in this case.

Feedback
Oct 21, 2021

11:00 pm - 11:08 pm (JST)

Author(s):

Stelios

Louka

(University of Cyprus)
Christos

K

Kourtellaris

(University of Cyprus)
Charalambos

D

Charalambous

(University of Cyprus)
Abstract:

In this paper we derive closed-form formulas of feedback capacity and nonfeedback achievable rates, for Additive Gaussian Noise (AGN) channels, driven by unstable i.e., nonstationary, autoregressive moving average (ARMA) noise (with one unstable pole and one unstable zero), based on channel inputs generated by optimal, two-parameter time-invariant feedback strategies or induced channel input distributions. From the analysis and simulations follows the surprising observations, (i) the use of time-invariant channel input distributions gives rise to multiple regimes of capacity that depend on the parameters of the ARMA noise, which may or may not use feedback, (ii) for an autoregressive noise, the higher the unstable pole the higher the capacity, (iii) for a moving average noise, the higher the unstable zero the higher the capacity, (iv) for the ARMA noise, as the pole and zero get closer together the capacity decreases.

11:08 pm - 11:16 pm (JST)

Author(s):

Stelios

Louka

(University of Cyprus)
Charalambos

D

Charalambous

(University of Cyprus)
Christos

K

Kourtellaris

(University of Cyprus)
Abstract:

The multiple-input multiple output (MIMO) generalization of Cover's and Pombra's Gaussian feedback capacity is considered. An equivalent sequential characterization of the finite block or transmission feedback information (FTFI) capacity is derived, with the optimal channel input processes expressed as functional of a sufficient statistic and a Gaussian orthogonal innovations process. From the new representations follows that the Cover and Pombra characterization of the FTFI capacity is expressed as a functional of two generalized matrix difference Riccati equations (DRE) of filtering theory of Gaussian systems. The new characterization, although, more complex than existing formulas that appeared in the literature, its sequential optimization formulation offers computational advantages, especially for MIMO channels.

Coding for Networks
Oct 21, 2021

11:00 pm - 11:08 pm (JST)

Author(s):

Hoover

H. F.

Yin

(The Chinese University of Hong Kong)
Xiaoli

Xu

(Southeast University)
Ka Hei

Ng

(The Chinese University of Hong Kong)
Yong Liang

Guan

(Nanyang Technological University)
Raymond W.

Yeung

(The Chinese University of Hong Kong)
Abstract:

Wireless relay network is a solution for transmitting information from a source node to a sink node far away by installing a relay in between. The broadcasting nature of wireless communication allows the sink node to receive part of the data sent by the source node. In this way, the relay does not need to receive the whole piece of data from the source node and it does not need to forward everything it received. In this paper, we consider the application of batched network coding, a practical form of random linear network coding, for a better utilization of such a network. The amount of innovative information at the relay which is not yet received by the sink node, called the innovative rank, plays a crucial role in various applications including the design of the transmission scheme and the analysis of the throughput. We present a visualization of the innovative rank which allows us to understand and derive formulae related to the innovative rank with ease.

11:08 pm - 11:16 pm (JST)

Author(s):

Manuj

Mukherjee

(Bar Ilan University)
Ran

Gelles

(Bar-Ilan University)
Abstract:

We consider computations over networks with multiple broadcast channels that intersect at a single party. Each broadcast link suffers from random bit-flip noise that affects the receivers independently. We design interactive coding schemes that successfully perform any computation over these noisy networks and strive to reduce their communication overhead with respect to the original (noiseless) computation. A simple variant of a coding scheme by Rajagopalan and Schulman (STOC 1994) shows that any (noiseless) protocol of ..R.. rounds can be reliably simulated in ..O(R\log n).. rounds over a network with ..n=n_1n_2+1.. parties in which a single party is connected to ..n_2.. noisy broadcast channels, each of which connects ..n_1.. distinct parties. We design new coding schemes with improved overheads. Our approach divides the network into four regimes according to the relationship between ..n_1.. and ..n_2... We employ a two-layer coding where the inner code protects each broadcast channel and is tailored to the specific conditions of the regime in consideration. The outer layer protects the computation in the network and is generally based on the scheme of Rajagopalan and Schulman, adapted to the case of broadcast channels. The overhead we obtain ranges from ..O(\log\log n_2).. to ..O(\log n_2 \frac{\log\log n_1}{\log n_1}).. and beats the trivial ..O(\log n).. overhead in all four regimes.

Quantum Codes
Oct 21, 2021

11:00 pm - 11:08 pm (JST)

Author(s):

Matias

Bilkis

(Autonomous University of Barcelona)
John

Calsamiglia

(Física Teòrica: Informació i Fenòmens Quàntics, Departament de Física, Universitat Autònoma de Barcelona)
Matteo

Rosati

(Física Teòrica: Informació i Fenòmens Quàntics, Departament de Física, Universitat Autònoma de Barcelona)
Abstract:

We study the problem of calibrating a quantum receiver for optical coherent states when transmitted on a quantum optical channel with variable transmissivity, a common model for long-distance optical-fiber and free/deep-space optical communication. We optimize the error probability of legacy receivers, such as Kennedy's and Dolinar's, on average with respect to the channel transmissivity distribution. We then compare our results with the ultimate error probability attainable by a general quantum device, computing the Helstrom bound for mixtures of coherent-state hypotheses, for the first time to our knowledge, and with homodyne measurements. Then, we employ a recently introduced library of shallow reinforcement learning methods, demonstrating that the receiver can be calibrated under practical conditions in real time, based only on training samples of the signals transmitted through the variable channel.

11:08 pm - 11:16 pm (JST)

Author(s):

Taro

Shibayama

(Chiba University)
Yingkai

Ouyang

(University of Sheffield)
Abstract:

In this paper, we prove the equivalence of inserting separable quantum states and deletions. Hence any quantum code that corrects deletions automatically corrects separable insertions. First, we describe the quantum insertion/deletion error using the Kraus operators. Next, we develop an algebra for commuting Kraus operators corresponding to insertions and deletions. Using this algebra, we prove the equivalence between quantum insertion codes and quantum deletion codes using the Knill-Laflamme conditions.

Machine Learning
Oct 18, 2021

Abstract:
One of the four invited sessions at ITW2021, this session has five presentations on machine learning for communications and related areas.

11:30 pm - 11:38 pm (JST)

Author(s):

Gerhard

Wunder

(Freie Universität Berlin & Heisenberg Communications and Information Theory Group)
Benedikt

Groß

(FU Berlin)
Rick

Fritschek

(Freie Universität Berlin)
Rafael

F.

Schaefer

(University of Siegen)
Abstract:

The Jensen inequality is a widely used tool in a multitude of fields, such as for example information theory and machine learning. It can be also used to derive other standard inequalities such as the inequality of arithmetic and geometric means or the Hölder inequality. In a probabilistic setting, the Jensen inequality describes the relationship between a convex function and the expected value. In this work, we want to look at the probabilistic setting from the reverse direction of the inequality. We show that under minimal constraints and with a proper scaling, the Jensen inequality can be reversed. We believe that the resulting tool can be helpful for many applications and provide the example of variational estimation of mutual information, where the reverse inequality leads to a new estimator with superior training behavior in comparison to state of the art estimators.

11:38 pm - 11:46 pm (JST)

Author(s):

Ezgi

Tekgul

(The University of Texas at Austin)
Thomas

Novlan

(AT&T Labs)
Salam

Akoum

(AT&T Labs)
Jeffrey

Andrews

(The University of Texas at Austin)
Abstract:

Finding an optimum configuration of base station (BS) antenna parameters is a challenging, non-convex problem for cellular networks. The chosen configuration has major implications for coverage and throughput in real-world systems, as it effects signal strength differently throughout the cell, as well as dictating the interference caused to other cells. In this paper, we propose a novel and sample-efficient data-driven methodology for optimizing antenna downtilt angles. Our approach combines Bayesian Optimization (BO) with Differential Evolution (DE): BO decreases the computational burden of DE, while DE helps BO avoid the curse of dimensionality. We evaluate the performance on a realistic state-of-the-art cellular system simulator developed by AT&T Labs, that includes all layers of the protocol stack and sophisticated channel models. Our results show that the proposed algorithm outperforms Bayesian optimization, random selection, and the baseline settings adopted in 3GPP by nontrivial amounts in terms of both capacity and coverage. Also, our approach is notably more time-efficient than DE alone.

11:46 pm - 11:54 pm (JST)

Author(s):

Hao

Jiang

(Tsinghua University)
Yu

Lu

(Tsinghua University)
Xueru

Li

(Huawei Technologies Co. LTD)
Bichai

Wang

(Tsinghua University)
Yongxing

Zhou

(Huawei)
Linglong

Dai

(Tsinghua University)
Abstract:

Hybrid precoding design is a high-complexity problem due to the coupling of analog and digital precoders as well as the constant modulus constraint for the analog precoder. Fortunately, the deep learning based hybrid precoding methods can significantly reduce the complexity, but the performance remains limited. In this paper, inspired by the attention mechanism recently developed for machine learning, we propose an attention-based hybrid precoding scheme for millimeter-wave (mmWave) MIMO systems with improved performance and low complexity. The key idea is to design each user's beam pattern according to its attention weights to other users'. Specifically, the proposed attention-based hybrid precoding scheme consists of two parts, i.e., the attention layer and the convolutional neural network (CNN) layer. The attention layer is used to identify the features of inter-user interferences. Then, these features are processed by the CNN layer for the analog precoder design to maximize the achievable sum-rate. Simulation results demonstrate that the attention layer could mitigate the inter-user interferences, and the proposed attention-based hybrid precoding with low complexity can achieve higher achievable sum-rate than the existing deep learning based method.

11:54 pm - 12:02 am (JST)

Author(s):

Haochuan

Song

(National Mobile Communications Research Laboratory, Southeast University)
Xiaohu

You

(National Mobile communication Research Lab., Southeast University)
Chuan

Zhang

(National Mobile Communications Research Laboratory, Southeast University)
Christoph

Studer

(ETH Zurich)
Abstract:

We propose a novel soft-output joint channel estimation and data detection (JED) algorithm for multiuser (MU) multiple-input multiple-output (MIMO) wireless communication systems. Our algorithm approximately solves a maximum a-posteriori JED optimization problem using deep unfolding and generates soft-output information for the transmitted bits in every iteration. The parameters of the unfolded algorithm are computed by a hyper-network that is trained with a binary cross entropy (BCE) loss. We evaluate the performance of our algorithm in a coded MU-MIMO system with 8 basestation antennas and 4 user equipments and compare it to state-of-the-art algorithms that separate channel estimation from soft-output data detection. Our results demonstrate that our JED algorithm outperforms such data detectors with as few as 10 iterations.

12:02 am - 12:10 am (JST)

Author(s):

Farhad

Mirkarimi

(Sharif University of Technology)
Stefano

Rini

(National Yangming Jiaotong University)
Nariman

Farsad

(Ryerson University)
Abstract:

Recently, several methods have been proposed for estimating information-theoretic measures, such as Kullback-Leibler divergence and mutual information from sample data using neural networks. These methods have been shown to achieve state-of-the-art performance, especially for high-dimensional data. Inspired by these results, a few new methods have been proposed for estimating the channel capacity from sample data without knowing the underlying channel models. In this work, we explore different techniques that can be used to estimate the capacity from sample data using neural networks. We then focus on several well-known point-to-point and multiple access channels and evaluate how neural capacity estimation performs compared to known results and bounds. We also focus on the learned input distribution by the neural capacity estimator and compare it to known optimal input distributions. Our results suggest that while neural capacity estimation may not be precise, it can be computationally efficient compared to other known numerical methods and can learn input distributions that are capacity-approaching.

Codes for Distributed Computing
Oct 19, 2021

Abstract:
One of the four invited sessions at ITW2021, this session has five presentations on coding for distributed computing.

11:30 pm - 11:38 pm (JST)

Author(s):

Anindya Bijoy

Das

(Iowa State University)
Aditya

Ramamoorthy

(Iowa State University)
Abstract:

The overall execution time of distributed matrix computations is often dominated by slow worker nodes (stragglers) over the clusters. Recently, different coding techniques have been utilized to mitigate the effect of stragglers where worker nodes are assigned the task of processing encoded submatrices of the original matrices. In many machine learning or optimization problems the relevant matrices are often sparse. Several coded computation methods operate with dense linear combinations of the original submatrices; this can significantly increase the worker node computation times and consequently the overall job execution time. Moreover, several existing techniques treat the stragglers as failures (erasures) and discard their computations. In this work, we present a coding approach which operates with limited encoding of the original submatrices and utilizes the partial computations done by the slower workers. Our scheme continues to have the optimal threshold of prior work. Extensive numerical experiments done in AWS (Amazon Web Services) cluster confirm that the proposed approach enhances the speed of the worker computations (and thus the whole process) significantly.

11:38 pm - 11:46 pm (JST)

Author(s):

Kannan

Ramchandran

(University of California at Berkeley)
Nived

Rajaraman

(University of California, Berkeley)
Swanand

Kadhe

(University of California, Berkeley)
Abstract:

Secret sharing is a fundamental security primitive that is widely used, finding application in modern settings like privacy-preserving federated learning. Conventional secret sharing methods, such as Shamir's celebrated scheme, distribute a secret judiciously to 'n' parties such that any fraction of the participants below a targeted threshold learn nothing about the secret, while a fraction above that threshold can recover the secret at O(n^2) computational cost. This quadratic cost limits the ability to scale secret sharing to only a limited number of participants, and is a barrier to applications like federated learning, where the number of clients is typically in the thousands. In this talk, we present FastShare - a novel multi-secret sharing scheme, powered by the (finite field) Fast Fourier Transform (FFT). FastShare critically leverages the non-adversarial nature of dropouts in federated learning, allowing for recovery from a random subset of the clients with O(n log n) computational cost. We highlight FastSecAgg, a secure aggregation protocol for federated learning that builds on top of FastShare and enables the central server to aggregate local client models in a privacy-preserving manner while being robust to client dropouts. FastSecAgg is particularly attractive when the number of model parameters is much larger than the number of clients, as is typical in federated learning.

11:46 pm - 11:54 pm (JST)

Author(s):

Francisco

Maturana

(Carnegie Mellon University)
Rashmi

Vinayak

(Carnegie Mellon University)
Abstract:

In large-scale data storage systems, erasure codes are employed to store data in a redundant fashion for reliability. In this setting, a set of k data blocks to be stored is encoded using an [n, k] code to generate n blocks that are then stored on distinct storage devices. In our recent work, we showed that the failure rate of storage devices vary significantly over time, and that dynamically tuning the parameters n and k of the code provides considerable reduction in storage cost. However, traditional codes suffer from prohibitively high resource overheads in changing the code parameters on already encoded data. Motivated by this application, we present a new theoretical framework formalizing "code conversion"-the process of converting data encoded with an [n, k] code into data encoded using a code with different parameters [n', k'] while maintaining desired decodability properties, such as the maximum-distance-separability (MDS) property. We introduce "convertible codes", a new class of codes that enable resource efficient conversions. We then derive lower bounds on the access and bandwidth costs of conversion for a wide range of parameter regimes and present explicit optimal constructions matching these lower bounds.

11:54 pm - 12:02 am (JST)

Author(s):

Chien-Sheng

Yang

(University of Southern California)
Jinhyun

So

(University of Southern California)
Chaoyang

He

(USC)
Songze

Li

(Hong Kong University of Science and Technology)
Qian

Yu

(University of Southern California)
Salman

Avestimehr

(University of Southern California)
Abstract:

Secure model aggregation is a key component of federated learning (FL) that aims at protecting the privacy of each user's individual model, while allowing their global aggregation. It can be applied to any aggregation-based approaches, including algorithms for training a global model (e.g., FedNova, FedProx, FedOpt), as well as personalized FL frameworks (e.g., pFedMe, Ditto, Per-FedAvg). Model aggregation needs to also be resilient to likely user dropouts in FL system, making its design substantially more complex. State-of-the-art secure aggregation protocols essentially rely on secret sharing of the random-seeds that are used for mask generations at the users, in order to enable the reconstruction and cancellation of those belonging to dropped users. The complexity of such approaches, however, grows substantially with the number of dropped users. We propose a new approach, named LightSecAgg, to overcome this bottleneck by turning the focus from ''random-seed reconstruction of the dropped users'' to ''one-shot aggregate-mask reconstruction of the active users''. More specifically, in LightSecAgg each user protects its local model by generating a single random mask. This mask is then encoded and shared to other users, in such a way that the aggregate-mask of any sufficiently large set of active users can be reconstructed directly at the server via encoded masks. We show that LightSecAgg achieves the same privacy and dropout-resiliency guarantees as the state-of-the-art protocols, while significantly reducing the overhead for resiliency to dropped users. Furthermore, our system optimization helps to hide the runtime cost of offline processing by parallelizing it with model training. We evaluate LightSecAgg via extensive experiments for training diverse models (logistic regression, shallow CNNs, MobileNetV3, and EfficientNet-B0) on various datasets (FEMNIST, CIFAR-100, GLD-23K) in a realistic FL system, and demonstrate that LightSecAgg significantly reduces the total training time, achieving a performance gain of up to 12.7x over baselines.

12:02 am - 12:10 am (JST)

Author(s):

Haewon

Jeong

(Carnegie Mellon University)
Abstract:

We study coded distributed matrix multiplication from an approximate recovery viewpoint. We consider a system of P computation nodes where each node stores 1/m of each multiplicand via linear encoding. Our main result shows that the matrix product can be recovered with ε relative error from any m of the P nodes for any ε > 0. We obtain this result through a careful specialization of MatDot codes --- a class of matrix multiplication codes previously developed in the context of exact recovery ε=0). Since prior results showed that MatDot codes achieve the best exact recovery threshold for a class of linear coding schemes, our result shows that allowing for mild approximations leads to a system that is nearly twice as efficient as exact reconstruction. For Entangled-Poly codes --- which are generalizations of MatDot codes --- we show that approximation reduces the recovery threshold from p^2 q + q -1 to p^2q, when the input matrices A, B are split respectively in to a p *q and q * p grids of equal-sized submatrices.

Information-Theoretic Security
Oct 20, 2021

Abstract:
One of the four invited sessions at ITW2021, this session has five presentations on information-theoretic security.

11:40 pm - 11:48 pm (JST)

Author(s):

Reihaneh

Safavi-Naini

(University of Calgary)
Setareh

Sharifian

(University of Calgary)
Abstract:

A hybrid encryption scheme uses a key encapsulation mechanism (KEM) to generate and establish a shared secret key with the decrypter, and a secret key data encapsulation mechanism (DEM) to encrypt the data using the key that is established by the DEM. The decrypter recovers the key using the ciphertext that is generated by the KEM, and uses it to decrypt the ciphertext that is generated by the DEM. We motivate and propose hybrid encryption in correlated randomness model where all participants including the eavesdropper, have access to samples of their respective correlated random variables. We define information-theoretic KEM (iKEM), and prove a composition theorem for iKEM and DEM that allows us to construct an efficient hybrid encryption system in correlated randomness model, providing post-quantum security. The construction uses an information-theoretic one-way secret key agreement (OW-SKA) protocol that satisfies a new security definition, and a one-time symmetric key encryption system that can be implemented by XORing the output of a (computationally) secure pseudorandom generator with the message. We discuss our results and directions for future work.

11:48 pm - 11:56 pm (JST)

Author(s):

Alexander

Koch

(Competence Center for Applied Security Technology (KASTEL), Karlsruhe Institute of Technology (KIT), Germany)
Abstract:

We survey several security assumptions based on physical principles as opposed to more common complexity-theoretic assumptions. This survey focuses on obtaining security guarantees via i) idealized hardware and ii) physical objects, and specifies how these assumptions have been used for devising cryptographic protocols, such as protocols for secure multi-party computation. Note that due to these assumptions, the protocols are often conceptually simpler, the security is independent of the computational power of an attacker, and the functioning and security is more transparent to humans.

11:56 pm - 12:04 am (JST)

Author(s):

Akinori

Kawachi

(Mie University)
Abstract:

The private simultaneous messages (PSM) model is a simple variant of the secure multiparty computation (MPC). In the k-party PSM model, each party Pi has a private input xi for i=1, ..., k. For a function f, each Pi encrypts xi into a message mi with a random string r shared among P1, ..., Pk, and sends mi to the referee R. R computes f(x1, ..., xk) from their respective messages m1, ..., mk. Then, R learns nothing from m1, ..., mk except for the output value f(x1, ..., xk). This simple model provides interesting cryptographic applications and is essential for understanding the intrinsic costs (e.g., of communication |m1| + ... + mk and randomness |r|) to achieve MPC. This study surveys recent results associated with the PSM and closely related models.

12:04 am - 12:12 am (JST)

Author(s):

Anderson

Nascimento

(University of Washington Tacoma)
Abstract:

Secure Multiparty Computation (MPC) is an invaluable tool for training machine learning models when the training data cannot be directly accessed by the model trainer. Unfortunately, complex algorithms, such as deep learning models, have their computational complexities increased by orders of magnitude when performed using MPC protocols. In this contribution, we study how to efficiently train an important class of machine learning problems by using MPC where features are known by one of the computing parties and only the labels are private. We propose new protocols combining differential privacy (DP) and MPC in order to privately and efficiently train a deep learning model in such scenario. More specifically, we release differentially private information during the MPC computation to dramatically reduce the training time. All released information does not compromise the privacy of the labels at the individual level. Our protocols can have running times that are orders of magnitude better than a straightforward use of MPC at a moderate cost in model accuracy.

12:12 am - 12:20 am (JST)

Author(s):

Kenji

Yasunaga

(Osaka University)
Abstract:

We usually prove the security of cryptographic primitives by assuming "ideal" probability distributions. In practice, we need to replace them with "real" distributions with preserving the security levels of the primitives. We demonstrate that the Hellinger distance is useful for measuring the closeness of distributions in this problem. To quantify the security levels of primitives, we employ two frameworks of bit security proposed by Micciancio and Walter (Eurocrypt 2018) and Watanabe and Yasunaga (Asiacrypt 2021). In both frameworks, approximating distributions in the Hellinger distance is effective, especially for decision-type primitives such as encryption schemes and pseudorandom generators.

Low Latency
Oct 21, 2021

Abstract:
One of the four invited sessions at ITW2021, this session has six presentations on low-latency coding and related areas.

11:20 pm - 11:28 pm (JST)

Author(s):

Lin

Zhou

(Beihang University)
Alfred

Hero III

(University of Michigan)
Yun

Wei

(Duke University)
Abstract:

Motivated by practical machine learning applications, we revisit the outlying sequence detection problem (Li et al., TIT 2014) and derive fundamental limits of optimal detection when the reject option is allowed for outlying sequences. In the considered outlying sequence detection (OSD) problem, one is given multiple observed sequences, where all sequences are generated i.i.d. from a nominal distribution with at most one exception. The task is to discern the outlying sequence that is generated according to an anomalous distribution. In OSD, the nominal and anomalous distributions are unknown. In this paper, we consider the case where there is a reject option for the OSD, i.e., we reject the samples as insufficient for making a reliable decision (cf. Bartlett et al., JMLR 2008). We study the tradeoff among the probabilities of misclassification error, false alarm and false reject for tests that satisfy weak conditions on the rate of decrease of these error probabilities as a function of sequence length. We propose a second-order asymptotically optimal test that provides a finite sample approximation to the error probabilities.

11:28 pm - 11:36 pm (JST)

Author(s):

Gonzalo

Vazquez-Vilar

(Universidad Carlos III de Madrid)
Abstract:

We study the channel-coding performance on an additive white Gaussian noise channel with different power limitations at the transmitter. While the meta-converse bound can be used to obtain lower bounds on the minimum error probability of the best coding scheme, it is required to solve an optimization problem over n-dimensional input distributions. This point hinders its application in several scenarios of interest. In this talk, we consider the optimization of the meta-converse bound with a certain auxiliary product distribution. Exploiting certain symmetries of the bound, we simplify and solve the optimization problem over input distributions for maximal and average power constraints. These bounds are tighter than previous results in the finite blocklength regime, and yield a better understanding on the structure of good codes under an average power limitation. While the results are specific for the power-constrained Gaussian channel, the techniques presented could be of interest in other settings.

11:36 pm - 11:44 pm (JST)

Author(s):

Recep Can

Yavas

(California Institute of Technology)
Victoria

Kostina

(California Institute of Technology)
Michelle

Effros

(California Institute of Technology)
Abstract:

This paper investigates variable-length feedback codes for discrete memoryless channels in point-to-point, multiple access, and random access communication. The proposed nested code employs ..L.. decoding times ..n_1, n_2, \dots, n_L.. for the point-to-point and multiple access channels and ..KL.. decoding times ..\{n_{k, \ell} \colon 1 \leq k \leq K, 1 \leq \ell \leq L\}.. for the random access channel with at most ..K.. active transmitters; in the latter case, decoding times ..n_{k, \ell}.., ..1 \leq \ell \leq L.. are reserved for decoding in the scenario where the decoder believes that the number of active transmitters is ..k... The code has a nested structure, i.e., codewords used to decode messages from ..k.. active transmitters are prefix of codewords used to decode messages from ..k + 1.. active transmitters. The code employs single-bit, scheduled feedback from the receiver to the transmitters at each potential decoding time to inform the transmitters whether or not it is able to decode. Transmitters cease transmission, thereby truncating their codewords, when no further transmissions are required by the decoder. The choice of decoding times is optimized to minimize the expected decoding time subject to an error probability constraint, and second order achievability bounds are derived.

11:44 pm - 11:52 pm (JST)

Author(s):

Lan

V.

Truong

(University of Cambridge)
Giuseppe

Cocco

(Universitat Pompeu Fabra)
Josep

Font-Segura

(Universitat Pompeu Fabra)
Albert

Guillén i Fàbregas

(ICREA and Universitat Pompeu Fabra & University of Cambridge)
Abstract:

This paper studies the error exponent of i.i.d. randomly generated codes used for transmission over discrete memoryless channels with maximum likelihood decoding. Specifically, this paper shows that the error exponent of a code, defined as the negative normalized logarithm of the probability of error, converges in probability to the typical error exponent. For high rates, the result is a consequence of the fact that the random-coding error exponent and the sphere-packing error exponent coincide. For low rates, the proof of convergence is based on the fact that the union bound accurately characterizes the probability of error.

11:52 pm - 12:00 am (JST)

Author(s):

Shih-Chun

Lin

(National Taiwan University)
Yi-Chun

Lai

(National Taiwan University of Science and Technology)
Yu-Chih

Huang

(National Chiao Tung University)
Chih-Chun

Wang

(Purdue University)
I-Hsiang

Wang

(National Taiwan University)
Abstract:

With the recent emergence of many low-latency applications over wireless networks, the need for accurate finite-length analysis of channel coding over multi-user wireless channels is ever increasing. This paper focuses exclusively on the two-user broadcast packet erasure channel (PEC) with causal feedback, for which existing results show that various linear network coding (LNC) schemes can attain the broadcast capacity region when the block length approaches infinity. Instead of the asymptotic capacity-based analysis, this work derives the exact value of the LNC based broadcast channel dispersion. Our approach is based on a new explicit characterization of the optimal LNC scheme under any arbitrarily given finite block length. The results show that among all existing asymptotically capacity-achieving LNC schemes, one (class) of them is provably finite-length optimal. By analyzing its second-order asymptotic, we have thus derived the exact (optimal) LNC broadcast channel dispersion, which closes the gap of the state-of-the-art inner and outer bounds previously derived in Lin et al. ISIT 2021

12:00 am - 12:08 am (JST)

Author(s):

Lei

Yu

(Nankai University)
Abstract:

In this paper, we derive sharp nonlinear dimension-free Brascamp-Lieb inequalities (including hypercontractivity inequalities) for distributions on Polish spaces, which strengthen the classic Brascamp-Lieb inequalities. Applications include the extension of Mrs. Gerber's lemmas to the cases of Rényi divergences and distributions on Polish spaces, the strengthening of small-set expansion theorems, and the characterization of the exponent of q-stability of Boolean functions. Our proofs in this paper are based on information-theoretic and coupling techniques.