Publication

On Speed and Advantage : Results in Information Velocity and Monitoring Problems

Reka Inovan
2024
EPFL thesis
Abstract

Information theory has allowed us to determine the fundamental limit of various communication and algorithmic problems, e.g., the channel coding problem, the compression problem, and the hypothesis testing problem. In this work, we revisit the assumptions underlying two of the classical information theoretic problems: the channel coding problem and the hypothesis testing problem. In the first part, we study the information velocity problem. If the channel coding problem answers the question of how much information we can send per time unit, the information velocity problem tackles the question of the latency of communicating said information on a communication network composed of relays. In the literature, this problem is commonly studied in the regime of finite message size but with a growing number of relays. In this work, we consider an asymptotic regime where we let the message size to grow to infinity. We present a converse result and two achievability results: one for Binary Erasure Channels (BEC) and one for Additive White Gaussian Noise (AWGN) channels with feedback. The converse result is obtained by extending the argument given in (Rajagopalan and Schulman, 1994) using the tools of F-divergences. The achievability results that we obtain are based on two different ideas. In the achievability result for BEC, we exploited the property of tree codes which ensure that all message bits can eventually be correctly decoded after a certain time delay. We use this property to build a tape abstraction which allows for the streaming of message bits through the relay chain. For AWGN channels, we modify the Schalkwijk-Kailath scheme to allow each relay to focus on locally transmitting its estimate of the message bits to its neighboring relay. We analyze the local behavior of this scheme, and show that we can prove results about the information velocity of the whole network based on these local results.In the second part we study the monitoring problem. This problem capture a scenario where several regular data-generating processes maximize their own reward, with one adversarial data-generating process hiding among these regular processes and privy to certain private information. This model introduces an interesting trade-off where the adversarial data-generating process aims to exploit its private information without deviating too much from the regular data-generating processes. As by increasing its deviation, it also becomes more distinguishable from the regular data generating processes. We will analyze this problem using tools from information theory and characterize the extent of the advantage that can be obtained by the adversarial data generation process. In doing so, we showed that classification problems, which are commonly modeled as hypothesis testing problems, become more complex when an adversarial data-generating process can adapt to the tester's protocol.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related concepts (34)
Error correction code
In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code or error correcting code (ECC). The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors.
Binary erasure channel
In coding theory and information theory, a binary erasure channel (BEC) is a communications channel model. A transmitter sends a bit (a zero or a one), and the receiver either receives the bit correctly, or with some probability receives a message that the bit was not received ("erased") . A binary erasure channel with erasure probability is a channel with binary input, ternary output, and probability of erasure . That is, let be the transmitted random variable with alphabet .
Algorithmic information theory
Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as strings or any other data structure. In other words, it is shown within algorithmic information theory that computational incompressibility "mimics" (except for a constant that only depends on the chosen universal programming language) the relations or inequalities found in information theory.
Show more
Related publications (111)

Symmetry in design and decoding of polar-like codes

Kirill Ivanov

The beginning of 21st century provided us with many answers about how to reach the channel capacity. Polarization and spatial coupling are two techniques for achieving the capacity of binary memoryless symmetric channels under low-complexity decoding algor ...
EPFL2022

On the Efficiency of Polar-Like Decoding for Symmetric Codes

Rüdiger Urbanke, Kirill Ivanov

The recently introduced polar codes constitute a breakthrough in coding theory due to their capacity-achieving property. This goes hand in hand with a quasilinear construction, encoding, and successive cancellation list decoding procedures based on the Plo ...
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Recursive Projection-Aggregation Decoding of Reed-Muller Codes

Emmanuel Abbé, Min Ye

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM code ...
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020
Show more
Related MOOCs (12)
Digital Signal Processing [retired]
The course provides a comprehensive overview of digital signal processing theory, covering discrete time, Fourier analysis, filter design, sampling, interpolation and quantization; it also includes a
Digital Signal Processing I
Basic signal processing concepts, Fourier analysis and filters. This module can be used as a starting point or a basic refresher in elementary DSP
Digital Signal Processing II
Adaptive signal processing, A/D and D/A. This module provides the basic tools for adaptive filtering and a solid mathematical framework for sampling and quantization
Show more

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.