Ke Shi: Almost tight [katex]\ell[/katex]-covering of [katex]\Z_n[/katex]

Speaker:

Ke Shi (University of Electronic Science and Technology of China)

Time:

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

Venue:

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.