אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב
וואי הנג'יה (אונ' בן-גוריון)
יום ראשון, 26.05.2019, 14:30
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.