SODA Conference 2016 Conference Paper
Robust positioning patterns
- Ross Berkowitz
- Swastik Kopparty
In this paper, we construct large sequences and matrices with the property that the contents of any small window determine the location of the window, robustly. Such objects have found many applications in practical settings, from positioning of wireless devices to smart pens, and have recently gained some theoretical interest. In this context, we give the first explicit constructions of sequences and matrices with high rate and constant relative distance. Accompanying these efficient constructions, we also give efficient decoding algorithms, which can determine the position of the window given its contents, even if a constant fraction of the contents have been corrupted.