Technical Program

Paper Detail

Paper IDA.4.2
Paper Title Maximum Length of Robust Positioning Sequences
Authors Duc Tu Dao, Han Mao Kiah, Nanyang Technological University, Singapore; Hengjia Wei, Ben-Gurion University of the Negev, Israel
Session A.4: Combinatorial Coding Theory I
Presentation Lecture
Track Algebraic and Combinatorial Coding Theory
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract An $(n,d)$-robust positioning sequence (RPS) is a binary sequence where every pair of length-$n$ subwords is distance $d$ apart. In this paper, we study the quantity $P(n,d)$, which denotes maximum length of an $(n,d)$-RPS, and provide tight estimates in the range $n/2 < d\le n$. First, we show that the usual Plotkin bound cannot be attained when certain divisibility conditions hold. Next, using the concept of differences, we construct an infinite family of RPSs that attain a modified Plotkin bound. Finally, except for 16 cases, we determine the {\em exact} values of $P(n,d)$ for $\delta(n) \le d\le n\le 50$, where $\delta(n)=\ceiling{n/2}$ if $n\not\equiv 0 \mod{4}$ and $\delta(n)=(n+2)/2$ if $n\not\equiv 0\mod{4}$

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!