TCS Lab Seminar: "Non-constructive approach to repetition thresholds"

Laboratory of Theoretical Computer Science will have the next online seminar on Wednesday, October 11, 18:10.

Zoom link                                                                                                                                                                                                                           

Title: Non-constructive approach to repetition thresholds

Speaker: Arseny M. Shur

Abstract: We analyze a simple algorithm, transforming an input word into a word avoiding certain repetitions such as fractional powers and undirected powers. This transformation can be made reversible by adding the log of the run of the algorithm to the output. We introduce a compression scheme for the logs; its analysis proves that $(1+\frac{1}{d})$-powers and undirected $(1+\frac{1}{d})$-powers can be avoided over $d+O(1)$ letters. These results are closer  to the optimum than it is usually expected from purely information-theoretic considerations.