Pseudorandom Generators For Low Degree Polynomials From Algebraic Geometry Codes.pdf

Problem:

A PRG for degree d polynomials is a function that, given a short seed, produces outputs indistinguishable from random elements in the corresponding field. The goal is to minimize the seed length (l) required for such a generator while ensuring effectiveness against all degree-d polynomials.

Previous Work:

The field has seen significant progress over the past decade:

- Early Results: Naor and Naor (1993) introduced small-bias sets, PRGs for linear functions (degree 1). Subsequent works improved seed lengths for constant degree polynomials.

- Breakthrough: Luby et al. (1993), later simplified by Viola (2007), constructed PRGs for constant degree polynomials over F2 with a non-optimal but significant seed length of 2√log n.

- Bogdanov (2005): Introduced the concept of "large fields" (fields of size dependent on n and d) achieving seed lengths of O(d4 log n) for all d. This relied on algebraic geometry techniques.

- Lu (2012): Improved upon Bogdanov's result, providing a PRG with better parameters (O(d6+c) field size) using O((d4/c)·log n) bits.

- Guruswami and Xing (2013): Recently proposed a PRG for fields of size O(d6) with seed length O(d4 log n).

Main Result:

This paper leverages the connection between PRGs and hitting set generators (HSGs) – functions that "hit" a large fraction of degree-d polynomials. They show:

1. Any good algebraic geometry code (a code with strong error-correcting properties) has a random subcode that acts as a HSG for degree-d polynomials.

2. Derandomization: By derandomizing this observation, they obtain a PRG with seed length O(d4 log n) and field size O(d12). The running time is npoly(d) but can be improved to poly(n, d) under certain assumptions about the explicitness of Riemann-Roch spaces.

Key Contribution:

The authors highlight their proof technique as a main contribution – a reduction from ensuring polynomial independence to avoiding collisions over the integers, heavily relying on the Riemann-Roch theorem. They believe this approach has broader implications in complexity theory.