Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Error correcting code:
TR22-129 | 15th September 2022
Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

Binary Codes with Resilience Beyond 1/4 via Interaction

In the reliable transmission problem, a sender, Alice, wishes to transmit a bit-string x to a remote receiver, Bob, over a binary channel with adversarial noise. The solution to this problem is to encode x using an error correcting code. As it is long known that the distance of binary ... more >>>

TR23-062 | 2nd May 2023
Benny Applebaum, Eliran Kachlon

Conflict Checkable and Decodable Codes and Their Applications

Let $C$ be an error-correcting code over a large alphabet $q$ of block length $n$, and assume that, a possibly corrupted, codeword $c$ is distributively stored among $n$ servers where the $i$th entry is being held by the $i$th server. Suppose that every pair of servers publicly announce whether the ... more >>>

TR24-110 | 1st July 2024
Joshua Cook, Dana Moshkovitz

Time and Space Efficient Deterministic Decoders

Time efficient decoding algorithms for error correcting codes often require linear space. However, locally decodable codes yield more efficient randomized decoders that run in time $n^{1+o(1)}$ and space $n^{o(1)}$. In this work we focus on deterministic decoding.
Gronemeier showed that any non-adaptive deterministic decoder for a good code running ... more >>>

ISSN 1433-8092 | Imprint