The Taub Faculty of Computer Science Events and Talks

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.