15 citations · 26 across the 10 of their papers we have counts for
17 papers
Discrepancy for Random Linear Codes
Dean Doron, Tal Leonov, Jonathan Mosheiff +3
We show that random linear codes (RLCs) possess nearly optimal discrepancy-type properties in a broad range of settings. Our main results are two general discrepancy theorems: one…
Fast Bounded-Independence Functions and Their Duals
Martijn Brehm, Yuval Ishai, Nicolas Resch
We continue the study of {\em fast} functions, computable by linear-size circuits, that share useful properties of random functions. Motivated by cryptographic applications, we gen…
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…
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-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 dep…
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 $…
Randomness-Efficient Constructions of Capacity-Achieving List-Decodable Codes
Jonathan Mosheiff, Nicolas Resch, Kuo Shang +1
We wish to generate list-decodable codes over small alphabets using as little randomness as possible. Specifically, we hope to generate codes achieving what we term the Elias bound…
Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes
Nicolas Resch, Chen Yuan, Yihan Zhang
In this work, we consider the list-decodability and list-recoverability of codes in the zero-rate regime. Briefly, a code is -list-recover…
Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery
Nicolas Resch, Chen Yuan, Yihan Zhang
In this work we consider the list-decodability and list-recoverability of arbitrary -ary codes, for all integer values of . A code is called -list-decodable if…
Threshold Rates of Codes Ensembles: Linear is Best
Nicolas Resch, Chen Yuan
In this work, we prove new results concerning the combinatorial properties of random linear codes. Firstly, we prove a lower bound on the list-size required for random linear codes…
Smoothing Codes and Lattices: Systematic Study and New Bounds
Thomas Debris-Alazard, Léo Ducas, Nicolas Resch +1
In this article we revisit smoothing bounds in parallel between lattices codes. Initially introduced by Micciancio and Regev, these bounds were instantiated with Gaussian dis…
Threshold rates for properties of random codes
Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch +2
Suppose that is a property that may be satisfied by a random code . For example, for some , might be the property that there exist three eleme…
Bounds for list-decoding and list-recovery of random linear codes
Venkatesan Guruswami, Ray Li, Jonathan Mosheiff +3
A family of error-correcting codes is list-decodable from error fraction if, for every code in the family, the number of codewords in any Hamming ball of fractional radius …
LDPC Codes Achieve List Decoding Capacity
Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi +2
We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have…
Coding for Interactive Communication with Small Memory and Applications to Robust Circuits
Bernhard Haeupler, Nicolas Resch
Classically, coding theory has been concerned with the problem of transmitting a single message in a format which is robust to noise. Recently, researchers have turned their attent…
On the List-Decodability of Random Linear Rank-Metric Codes
Venkatesan Guruswami, Nicolas Resch
The list-decodability of random linear rank-metric codes is shown to match that of random rank-metric codes. Specifically, an -linear rank-metric code over $\mathbb{F…