4 papers
Optimal PRGs for Low-Degree Polynomials over Polynomial-Size Fields
Gil Cohen, Dean Doron, Noam Goldgraber
Pseudorandom generators (PRGs) for low-degree polynomials are a central object in pseudorandomness, with applications to circuit lower bounds and derandomization. Viola's celebrate…
Tracing AG Codes: Toward Meeting the Gilbert-Varshamov Bound
Gil Cohen, Dean Doron, Noam Goldgraber +1
One of the oldest problems in coding theory is to match the Gilbert-Varshamov bound with explicit binary codes. Over larger-yet still constant-sized-fields, algebraic-geometry code…
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…
Nearly-Linear Time Seeded Extractors with Short Seeds
Dean Doron, João Ribeiro
Seeded extractors are fundamental objects in pseudorandomness and cryptography, and a deep line of work has designed polynomial-time seeded extractors with nearly-optimal parameter…