Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Coding Theory: Nearly Optimal Robust Positioning Sequences
event speaker icon
Wei Hengjia (Ben-Gurion University)
event date icon
Sunday, 26.05.2019, 14:30
event location icon
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.