This paper studies when list-decodability guarantees for error-correcting codes of good distance can go beyond the classical Johnson radius and gives a corresponding efficient list-decoding algorithm for Reed-Solomon codes up to this new radius. The Johnson bound shows that any error-correcting code with distance $\del...
We revisit a classical result of Coppersmith and Shparlinski 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 D...
We study the problem of constructing highly nonlinear vectorial maps $F: \mathbb F_2^n \to \mathbb F_2^m$. Concretely, we want an $F$ and an $A = A(m,n)>0$ as small as possible, so that for every affine map $L: \mathbb F_2^n \to \mathbb F_2^m$ (of the form $L(x) = M x + b $) we have: $$\mathrm{agree}(F, L) := |\{ x \in...
S. Kopparty, Rishabh Kothary, Shanthanu S. Rai· Electron. Colloquium Comput....· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.