Vibe Proof

Entries

• lax-100001Reconstructing Binary Words of Unknown Length with #-Subword Queries

  A guesser reconstructs a binary word $w$ of unknown length $n$. A #-subword query gives the number of occurrences of a chosen word $u$ as a subword of $w$. Querying $0$ and $1$ gives the length. A deterministic algorithm reconstructs $w$ in $O(\sqrt{\log n\,\log\log n})$ queries. A second deterministic algorithm uses only Lyndon words for $0<1$ and makes $O(\log(n+2))$ queries. Both bounds count the first two queries and hold for every $w$.

  Lean sources: lax-100001-source.tar.gz