8 papers · 1 filter
Discrepancy for Random Linear Codes
Dean Doron, Tal Leonov, Jonathan Mosheiff +3
We prove that random linear codes have nearly optimal discrepancy properties in a broad range of regimes. Our main results are two general theorems: one controlling all translates…
Linear time encodable binary code achieving GV bound with linear time encodable dual achieving GV bound
Martijn Brehm, Nicolas Resch
We initiate the study of what we term ``fast good codes'' with ``fast good duals.'' Specifically, we consider the task of constructing a rate 1/2 binary linear code such that both…
List Recoverable Codes: The Good, the Bad, and the Unknown (hopefully not Ugly)
Nicolas Resch, S. Venkitesh
List recovery is a fundamental task for error-correcting codes, vastly generalizing unique decoding from worst-case errors and list decoding. Briefly, one is given ''soft informati…
List-Recovery of Random Linear Codes over Small Fields
Dean Doron, Jonathan Mosheiff, Nicolas Resch +1
We study list-recoverability of random linear codes over small fields, both from errors and from erasures. We consider codes of rate -close to capacity, and aim to bound the de…
On the Independence Assumption in Quasi-Cyclic Code-Based Cryptography
Maxime Bombar, Nicolas Resch, Emiel Wiedijk
Cryptography based on the presumed hardness of decoding codes -- i.e., code-based cryptography -- has recently seen increased interest due to its plausible security against quantum…
Interactive Coding with Small Memory and Improved Rate
Dorsa Fathollahi, Bernhard Haeupler, Nicolas Resch +1
In this work, we study two-party interactive coding for adversarial noise, when both parties have limited memory. We show how to convert any adaptive protocol into a protocol…