Publications associées à Linear network coding

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

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 ...

EPFL2024

Optima Age Over Erasure Channels

Emre Telatar, Elie Najm, Rajai Nasser

Previous works on age of information and erasure channels have dealt with specific models and computed the average age or average peak age for certain settings. In this paper, given a source that produces a letter every T-s seconds and an erasure channel t ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!

Rachid Guerraoui, Jovan Komatovic, Vincent Gramoli, Pierre Philippe Civit, Seth Gilbert, Manuel José Ribeiro Vidigueira

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether ...

Dagstuhl Publishing2022

On Codes Decoding a Constant Fraction of Errors on the BSC

Jan Hazla

We strengthen the results from a recent work by the second author, achieving bounds on the weight distribution of binary linear codes that are successful under block-MAP (as well as bit-MAP) decoding on the BEC. We conclude that a linear code that is succe ...

ASSOC COMPUTING MACHINERY2021

Three-Dimensional Cubic Barcodes

Martin Vetterli, Adam James Scholefield, Golnooshsadat Elhami

We consider three-dimensional cubic barcodes, consisting of smaller cubes, each built from one of two possible materials and carry one bit of information. To retrieve the information stored in the barcode, we measure a 2-D projection of the barcode using a ...

2022

Compute-Forward for DMCs: Simultaneous Decoding of Multiple Combinations

Michael Christoph Gastpar, Sung Hoon Lim, Adriano Pastore, Chen Feng

Algebraic network information theory is an emerging facet of network information theory, studying the achievable rates of random code ensembles that have algebraic structure, such as random linear codes. A distinguishing feature is that linear combinations ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Cooperative Data Exchange and Private Information Retrieval

Su Li

Coding techniques have been well studied and used for improving communication quality by combating noise and mitigating interference. Recently, it has been shown that the same coding techniques can also be exploited to further improve communication perform ...

EPFL2020

An Explicit Construction of Optimal Streaming Codes for Channels With Burst and Arbitrary Erasures

Damian Dudzicz

This paper presents a new construction of error correcting codes which achieves optimal recovery of a streaming source over a packet erasure channel. The channel model considered is the sliding-window erasure model, with burst and arbitrary losses, introdu ...

2020

On the Computational Complexity of Blind Detection of Binary Linear Codes

Alexios Konstantinos Balatsoukas Stimming, Aris Filos Ratsikas

In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish to find a code in a set of linear codes C of a given dimension k, for which t ...

IEEE2019

New Results On The Pseudoredundancy

Jens Markus Zumbrägel, Zihui Liu

The concepts of pseudocodeword and pseudoweight play a fundamental role in the finite-length analysis of LDPC codes. The pseudoredundancy of a binary linear code is defined as the minimum number of rows in a parity-check matrix such that the corresponding ...

2019