BARC talk by Ashutosh Shankar

Friday, November 6, 2026, 14:01-15:00, Ashutosh Shankar, PhD Student at TIFR Mumbai, India, will be giving a BARC talk on "Bounds on polynomial approximations of the discrete log function".

Abstract:
A classical result of Coppersmith and Shparlinski shows bounds on how well polynomials can approximate the discrete logarithm function. They showed that any univariate polynomial $f(X) \in \F_p[X]$ with $\deg(f) \leq D$ can agree with the discrete logarithm on at most $\sqrt{2 D p}$ points.
In our work, we improve the upper bound above to $(1+o(1)) \cdot \sqrt{Dp}$.
This new upper bound is the Johnson bound from the theory of list-decoding of error-correcting codes, and in fact our proof uses a connection to that problem. [CS00] also define an analogue of the problem with bivariate polynomials, and we improve that bound as well.
Additionally, for $D = 1$, where both the above bounds are $O(\sqrt{p})$, we give an asymptotically improved upper bound of $O(p^{2/5})$. In our proofs, we use various connections to additive combinatorics.

Based on joint work with Swastik Kopparty and Rishabh Kothary.

Bio:
Ashutosh Shankar is a final-year PhD student at TIFR, Mumbai. He is interested in coding theory, complexity, and lately in quantum computing. This is his first time in Copenhagen so please recommend him nice cafes and bars.

Host:
Varun Ramanathan