Algorithms and Logic Group


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

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:

B1-518B, Research Building 4

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.