6 papers
Algebraic-Geometric Parvaresh--Vardy Subspace Designs and Rank Condensers
Gil Cohen, Dean Doron, Noam Goldgraber
A subspace design is a collection of subspaces of with the property that no low-dimensional subspace intersects the collection "too much". Sub…
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…
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…
Full Galois groups of polynomials with slowly growing coefficients
Lior Bary-Soroker, Noam Goldgraber
Choose a polynomial uniformly at random from the set of all monic polynomials of degree with integer coefficients in the box . The main result of the paper assert…
Product Sets of Arithmetic Progressions in Function Fields
Lior Bary-Soroker, Noam Goldgraber
We study product sets of finite arithmetic progressions of polynomials over a finite field. We prove a lower bound for the size of the product set, uniform in a wide range of param…