Coding Theory: Nearly Optimal Robust Positioning Sequences

Wei Hengjia (Ben-Gurion University)
Sunday, 26.5.2019, 14:30
Taub 601

A robust positioning pattern is a large array that allows a mobile device to locate its position by reading a possibly corrupted small window around it. In this talk, we focus on the 1-dimensional case, i.e., robust positioning sequences (RPS). We present constructions of RPSs along with efficient locating algorithms. In particular, we construct a class of q-ary RPSs which are robust to a constant fraction of errors and have asymptotically optimal rate. We also obtain a class of binary RPSs which are robust to a constant number of errors, and the redundancy of the proposed sequences differs from the lower bound only by a small term.

Back to the index of events