Algebraic and Combinatorial Coding Theory
A.4.2
Lecture
Combinatorial Coding Theory I

# Maximum Length of Robust Positioning Sequences

Duc Tu Dao, Han Mao Kiah, Hengjia Wei

## Date & Time

01:00 am – 01:00 am

## 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}$

## Presenters

#### Duc Tu Dao

Nanyang Technological University

#### Han Mao Kiah

Nanyang Technological University

#### Hengjia Wei

Ben-Gurion University of the Negev

Paper

## Session Chair

#### Navin Kashyap

Indian Institute of Science