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.