7 papers
A Forward-Backward Weight Analysis of INW for Permutation Branching Programs
Gil Cohen, Dean Doron, Noam Goldgraber
We construct an -error PRG for permutation read-once branching programs of length and width with seed length \[ O\left((\log w+\log(1/\varepsilon))\cdot \log n…
The Insertion List-Decoding Capacity and an Improved Bound on the Deletion List-Decoding Capacity
Roni Con, Dean Doron, João Ribeiro
Informally, the capacity of list-decoding in a given adversarial error model is the largest rate at which we can list-decode with list size polynomial in the block length. The capa…
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…
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…
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…
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…