Ke Shi: Almost tight $\ell$-covering of $\Z_n$

Abstract

Let set $[\ell]=\{0,1,2,\ldots,\ell\}$. A subset $S$ of ring $\Z_n$ is called a $\ell$-covering set if $S[\ell] = \{ ab \mod n| a\in S, b\in [\ell]\} = \Z_n$. In the design of error correcting codes for limited-magnitude errors, small $\ell$-covering sets are used as a building block. We show there exists a $\ell$-covering sets of $\Z_n$ of size $O(\frac{n}{\ell}\log n\log \log n)$ for all $n$ and $\ell\leq n$ .
We consider a fast randomized construction algorithm that obtains a covering set of size at most $O(\log n)$ factor larger than the optimum covering set, and use on average $\tilde{O}(1)$ time per element in the $\ell$-covering set. We also show examples where the $\ell$-covering set must have size $\Omega(\frac{n}{\ell}\frac{\log n}{\log \log n})$. The proofs use results in sieve theory and symmetric linear programs.

Slides.

Schedule

• 16:20-17:20 (Time in Beijing)
• 21:20-22:20 (Time in Auckland)
• June 10, 2022 (Friday)