| Title | : | Word reconstruction using Lyndon subword queries |
| Speaker | : | Bhabya Deep Rai (IIT Madras) |
| Details | : | Tue, Oct 27, 2026 4:00 PM, @ SSB334 |
| Abstract | : | Suppose a fixed binary word (w) of length n is hidden from us. We can query a word u and learn how many times u occurs as a subword of w. In this setting, how many queries are needed to reconstruct w? Richomme and Rosenfeld (STACS 2023) showed that O(sqrt(n log n)) queries are sufficient to exactly reconstruct any word of length n. Fleischmann, Lejeune, Manea, Nowotka, and Rigo (DLT 2020) showed that if the queries asked are restricted to be of the form 0^k 1, then min(a,b) queries are sufficient, where a and b are the number of 0s and 1s in w respectively. We explore the query complexity of the problem when the queries are allowed to be only Lyndon words i.e. words that are lexicographically least among all its non-trivial cyclic rotations of the word. Lyndon words are a rich and well studied family of words that capture subword information particularly well, hence are a natural restriction for word reconstruction. In this work, we present two results: 1. We show a deterministic query algorithm that reconstructs a binary word w using at most O(k log n) Lyndon queries, where k is the number of 01-factors in w. This improves the above algorithm for appropriate range of values of k. 2. We also show that there is a randomized query algorithm that, with high probability, reconstructs w using at most 2^{O(sqrt(log n)/epsilon)} queries correct up to a fraction of (1-epsilon) of the entire word. This not only significantly improves upon the min(a,b) Lyndon subword query bound established by Fleischmann et al, but also outperforms the deterministic O(sqrt{n log n}) general subword counting query complexity proved by Richomme and Rosenfeld (which explicitly uses subword queries that are not Lyndon words). The main technical ingredient we establish and use is a correspondence between subword counting queries and counting bipartite order-induced subgraph queries in a specialized class of bipartite graphs called Parikh graphs. The structural properties of the bipartite adjacency matrix of Parikh graphs enable us to yield a better upper bound in terms of k. We associate a monotone Boolean function to the word using this connection, and use PAC learning algorithm for monotone functions by Bshouty and Tamon (JACM 1996) to approximately reconstruct our word, where we simulate queries for the Boolean function using Lyndon-subword queries. This talk is based on a joint work with Jayalal Sarma (to appear at FSTTCS 2026). |