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 >>>

Determining the communication complexity of graph connectivity has been one of the longest standing open problems in communication complexity since the seminal work of Babai, Frankl, and Simon [FOCS'86]. A simple protocol transmits a spanning forest using $O(N\log N)$ communication on $N$-vertex graphs. While this was shown optimal for deterministic ... more >>>