The question of whether the Gilbert-Varshamov bound (1952, 1957) gives the optimal tradeoff between rate and distance is one of the most fundamental in coding theory. It is a central instance of the broader question of how far algebraic structure can surpass the benchmark provided by the probabilistic method.

In ... more >>>

We revisit a classical result of Coppersmith and Shparlinski [CS00] showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $\deg(f) \leq D$, we have:
$$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = dlog(x) \}| \leq \sqrt{2 ... more >>>

We study the subclass of $\mathrm{prAM}$ problems such that derandomizing the corresponding Arthur--Merlin verifier (i.e. to an $\mathrm{NP}$ verifier) reduces to the Range Avoidance problem ($\mathrm{Avoid}$), the total search problem of finding a string outside the range of an expanding circuit.

We prove a new ... more >>>