pith. machine review for the scientific record. sign in

arxiv: 2604.19371 · v1 · submitted 2026-04-21 · 💻 cs.DS

Recognition: unknown

Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms

Jonas Ellert, Panagiotis Charalampopoulos, Pawe{\l} Gawrychowski, Taha El Ghazi, Tatiana Starikovskaya

Pith reviewed 2026-05-10 01:41 UTC · model grok-4.3

classification 💻 cs.DS
keywords asymmetric streamingsuffix random accessfunction inversionstring synchronizing setspattern matchingLempel-Ziv compressionstreaming algorithms
0
0 comments X

The pith

A bidirectional reduction between suffix random access and function inversion enables asymmetric streaming algorithms for string problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a bidirectional reduction showing that suffix random access reduces to function inversion and vice versa. Suffix random access maintains constant-time queries for the longest suffix of the streamed text prefix that appears in the reference string. This reduction serves as a generic tool to convert classical string algorithms into the asymmetric streaming model, in which the short reference string is available in read-only memory while the long text arrives symbol by symbol under a sublinear space bound. The authors also construct a locally sparse variant of string synchronizing sets that supports a single-pass streaming algorithm. A reader should care because the reduction lifts multiple existing algorithms for pattern matching and compression into the streaming setting while improving their resource bounds.

Core claim

We show a bidirectional reduction between suffix random access and function inversion, a central problem in cryptography. On the way we propose a variant of the string synchronizing sets with a local sparsity condition that admits an efficient streaming construction algorithm. This framework reduces fundamental string problems in the asymmetric streaming model to the online read-only model, yielding algorithms for exact and approximate pattern matching under Hamming and edit distances as well as relative Lempel-Ziv compression.

What carries the argument

The suffix random access data structure, which maintains constant-time random access to the longest suffix of the seen prefix of the text that occurs in the reference string, realized through reduction to a function-inversion oracle.

If this is right

  • Exact pattern matching becomes possible in the asymmetric streaming model with sublinear space.
  • Approximate pattern matching under Hamming distance obtains improved bounds via the same reduction.
  • Approximate pattern matching under edit distance obtains improved bounds via the same reduction.
  • Relative Lempel-Ziv compression admits an efficient asymmetric streaming solution.
  • Any future improvement to function inversion directly improves the string algorithms in this model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Hardness results for function inversion would translate into limitations on the power of asymmetric streaming for string problems.
  • The locally sparse synchronizing sets may apply to other streaming string tasks that currently lack sublinear-space solutions.
  • The reduction suggests a route for importing further cryptographic primitives into streaming string algorithms.

Load-bearing premise

That locally sparse string synchronizing sets can be built in one streaming pass with sublinear space and that the function-inversion oracle can be implemented to achieve the claimed time bounds in the asymmetric model.

What would settle it

An input text and reference pair on which no sublinear-space single-pass streaming algorithm exists for the locally sparse synchronizing sets, or on which the derived algorithms exceed the stated time bounds.

Figures

Figures reproduced from arXiv: 2604.19371 by Jonas Ellert, Panagiotis Charalampopoulos, Pawe{\l} Gawrychowski, Taha El Ghazi, Tatiana Starikovskaya.

Figure 1
Figure 1. Figure 1: Trade-offs for suffix random access data structures in a doubly-logarithmic scale. Each [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Text partitioning for the proof of Theorem 4.7. After [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Data structure layout from the proof of Lemma 4.11 using [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Random access data structures for the reference from the proof of Lemma 6.1. An arrow [PITH_FULL_IMAGE:figures/full_fig_p031_4.png] view at source ↗
read the original abstract

Many string processing problems can be phrased in the streaming setting, where the input arrives symbol by symbol and we have sublinear working space. The area of streaming algorithms for string processing has flourished since the seminal work of Porat and Porat [FOCS 2009]. Unfortunately, problems with efficient solutions in the classical setting often do not admit efficient solutions in the streaming setting. As a bridge between these two settings, Saks and Seshadhri [SODA 2013] introduced the asymmetric streaming model. Here, one is given read-only access to a (typically short) reference string $R$ of length $m$, while a text $T$ arrives as a stream. We provide a generic technique to reduce fundamental string problems in the asymmetric streaming model to the online read-only model, lifting several existing algorithms and generally improving upon the state of the art. Most notably, we obtain asymmetric streaming algorithms for exact and approximate pattern matching (under both the Hamming and edit distances), and for relative Lempel-Ziv compression. At the heart of our approach lies a novel tool that facilitates efficient computation in the asymmetric streaming model: the suffix random access data structure. In its simplest variant, it maintains constant-time random access to the longest suffix of (the seen prefix of) $T$ that occurs in $R$. We show a bidirectional reduction between suffix random access and function inversion, a central problem in cryptography. On the way to our upper bound, we propose a variant of the string synchronizing sets ([Kempa and Kociumaka; STOC 2019]) with a local sparsity condition that, as we show, admits an efficient streaming construction algorithm. We believe that our framework and techniques will find broad applications in the development of small-space string algorithms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript introduces a suffix random access data structure for the asymmetric streaming model (read-only reference string R of length m, streaming text T of length n) that supports constant-time access to the longest suffix of the seen prefix of T occurring in R. It establishes a bidirectional reduction between this data structure and the function-inversion problem, proposes a locally sparse variant of string synchronizing sets admitting a single-pass streaming construction with sublinear space, and applies the framework to obtain improved asymmetric streaming algorithms for exact/approximate pattern matching (Hamming and edit distances) and relative Lempel-Ziv compression by reducing them to the online read-only model.

Significance. If the reductions and constructions hold, the work supplies a generic technique for lifting classical string algorithms into the asymmetric streaming setting while improving time and space bounds for several core problems. The explicit bidirectional link to function inversion is a novel bridge between cryptography and streaming string algorithms; the locally sparse synchronizing sets, constructed via local windows and hash representatives in one pass with o(n) space, constitute an independent technical contribution that may apply to other small-space string problems.

minor comments (3)
  1. [Abstract] Abstract: the claimed time bounds for the pattern-matching and compression applications are stated only qualitatively; adding the precise dependence on the inversion-oracle cost and on m,n would allow immediate comparison with prior asymmetric-streaming results.
  2. [Section on locally sparse synchronizing sets] The definition of the locally sparse synchronizing set (around the construction in the streaming pass) uses a local-window parameter whose exact value is not pinned down in the high-level description; a concrete setting (e.g., window size log n or polylog n) would clarify the sparsity guarantee.
  3. [Reduction section] Figure 1 (or the diagram illustrating the reduction) would benefit from explicit arrows showing how the asymmetric-streaming space bound is preserved in both directions of the reduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The report correctly identifies the core contributions of the bidirectional reduction to function inversion and the streaming construction of locally sparse synchronizing sets. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central claims rest on an explicit bidirectional reduction mapping suffix random access to the external cryptographic problem of function inversion (and vice versa), together with a new locally sparse variant of string synchronizing sets whose single-pass streaming construction is derived directly from the local sparsity condition and hash-based representatives. These steps are self-contained: the time bounds follow from the oracle without additional self-referential fitting, and the cited prior work on synchronizing sets is external (Kempa-Kociumaka STOC 2019) rather than a load-bearing self-citation chain. No equation or construction reduces by definition to its own inputs, and the asymmetric streaming applications are obtained by composition rather than renaming or smuggling an ansatz.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The work rests on the standard definition of the asymmetric streaming model and on the existence of an efficient function-inversion primitive; it introduces the suffix-random-access structure and the locally sparse synchronizing-set variant as new objects.

axioms (1)
  • domain assumption Asymmetric streaming model: read-only random access to short reference R, one-way stream of T, sublinear working space.
    Invoked in the opening paragraphs to define the setting.
invented entities (1)
  • suffix random access data structure no independent evidence
    purpose: Provide constant-time random access to the longest suffix of the seen prefix of T that occurs in R.
    Introduced as the central new tool; no independent evidence supplied beyond the claimed reduction.

pith-pipeline@v0.9.0 · 5658 in / 1287 out tokens · 41503 ms · 2026-05-10T01:41:29.564969+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

109 extracted references · 95 canonical work pages · 1 internal anchor

  1. [1]

    PRIMES is in P.Ann

    Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P.Ann. Math., 160(2):781–793, 2004.doi:10.4007/annals.2004.160.781

    work page doi:10.4007/annals.2004.160.781 2004

  2. [2]

    Riva Shalom

    Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom. Mind the gap! - online dictionary matching with one gap.Algorithmica, 81(6):2123–2157, 2019.doi:10.1007/S00453-018-0526-2

    work page doi:10.1007/s00453-018-0526-2 2019

  3. [3]

    Riva Shalom

    Amihood Amir, Avivit Levy, Ely Porat, and B. Riva Shalom. Dictionary matching with a few gaps.Theor. Comput. Sci, 589:34–46, 2015.doi:10.1016/j.tcs.2015.04.011

    work page doi:10.1016/j.tcs.2015.04.011 2015

  4. [4]

    Polylogarithmic approximation for edit distance and the asymmetric query complexity

    Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Polylogarithmic approximation for edit distance and the asymmetric query complexity. InProc. of FOCS, pages 377–386, 2010.doi:10.1109/FOCS.2010.43

    work page doi:10.1109/focs.2010.43 2010

  5. [5]

    Faster Online Elastic Degenerate String Matching

    Kotaro Aoyama, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Faster Online Elastic Degenerate String Matching. InProc. of CPM, pages 9:1–9:10, Dagstuhl, Germany, 2018.doi:10.4230/LIPIcs.CPM.2018.9. 49

    work page doi:10.4230/lipics.cpm.2018.9 2018

  6. [6]

    Lorraine A. K. Ayad, Grigorios Loukides, Solon P. Pissis, and Hilde Verbeek. Sparse suffix and LCP array: Simple, direct, small, and fast. InProc. of LATIN (1), pages 162–177, 2024. doi:10.1007/978-3-031-55598-5_11

    work page doi:10.1007/978-3-031-55598-5_11 2024

  7. [7]

    Streaming al- gorithms for language recognition problems.Theor

    Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, and Girish Varma. Streaming al- gorithms for language recognition problems.Theor. Comput. Sci., 494:13–23, 2013.doi: 10.1016/J.TCS.2012.12.028

    work page doi:10.1016/j.tcs.2012.12.028 2013

  8. [8]

    Internal pattern matching in small space and applications

    Gabriel Bathie, Panagiotis Charalampopoulos, and Tatiana Starikovskaya. Internal pattern matching in small space and applications. InProc. of CPM, pages 4:1–4:20, 2024.doi: 10.4230/LIPICS.CPM.2024.4

    work page doi:10.4230/lipics.cpm.2024.4 2024

  9. [9]

    Small-space algorithms for the online language distance problem for palindromes and squares

    Gabriel Bathie, Tomasz Kociumaka, and Tatiana Starikovskaya. Small-space algorithms for the online language distance problem for palindromes and squares. InProc. of ISAAC, pages 10:1–10:17, 2023.doi:10.4230/LIPICS.ISAAC.2023.10

    work page doi:10.4230/lipics.isaac.2023.10 2023

  10. [10]

    Property testing of regular languages with ap- plications to streaming property testing of visibly pushdown languages

    Gabriel Bathie and Tatiana Starikovskaya. Property testing of regular languages with ap- plications to streaming property testing of visibly pushdown languages. InProc. of ICALP, pages 119:1–119:17, 2021.doi:10.4230/LIPICS.ICALP.2021.119

    work page doi:10.4230/lipics.icalp.2021.119 2021

  11. [11]

    Time-spacetradeoffsforbranchingprograms

    PaulBeame, T.S.Jayram, andMichaelE.Saks. Time-spacetradeoffsforbranchingprograms. J. Comput. Syst. Sci., 63(4):542–572, 2001.doi:10.1006/JCSS.2001.1778

    work page doi:10.1006/jcss.2001.1778 2001

  12. [12]

    Puglisi, and Rajeev Raman

    Djamal Belazzougui, Dmitry Kosolobov, Simon J. Puglisi, and Rajeev Raman. Weighted ancestors in suffix trees revisited. InProc. of CPM, pages 8:1–8:15, 2021.doi:10.4230/ LIPIcs.CPM.2021.8

    2021

  13. [13]

    Pissis, Leen Stougie, Michelle Sweering, and Wiktor Zuba

    Giulia Bernardini, Estéban Gabory, Solon P. Pissis, Leen Stougie, Michelle Sweering, and Wiktor Zuba. Elastic-degenerate string matching with 1 error or mismatch.Theory Comput. Syst., 68(5):1442–1467, 2024.doi:10.1007/S00224-024-10194-8

    work page doi:10.1007/s00224-024-10194-8 2024

  14. [14]

    Pissis, and Giovanna Rosone

    Giulia Bernardini, Paweł Gawrychowski, Nadia Pisanti, Solon P. Pissis, and Giovanna Rosone. Elastic-degenerate string matching via fast matrix multiplication.SIAM J. Comput, 51(3):549–576, 2022.doi:10.1137/20M1368033

    work page doi:10.1137/20m1368033 2022

  15. [15]

    Pissis, and Giovanna Rosone

    Giulia Bernardini, Nadia Pisanti, Solon P. Pissis, and Giovanna Rosone. Approximate pattern matching on elastic-degenerate text.Theor. Comput. Sci, 812:109–122, 2020. In memoriam Danny Breslauer (1968-2017).doi:10.1016/j.tcs.2019.08.012

    work page doi:10.1016/j.tcs.2019.08.012 2020

  16. [17]

    String matching with variable length gaps.Theor

    Philip Bille, Inge Li Gørtz, Hjalte Wedel Vildhøj, and David Kofoed Wind. String matching with variable length gaps.Theor. Comput. Sci, 443:25–34, 2012.doi:10.1016/j.tcs.2012. 03.029

    work page doi:10.1016/j.tcs.2012 2012

  17. [18]

    Allan Borodin and Stephen A. Cook. A time-space tradeoff for sorting on a general sequential model of computation.SIAM J. Comput., 11(2):287–297, 1982.doi:10.1137/0211022

    work page doi:10.1137/0211022 1982

  18. [19]

    Simple real-time constant-space string matching.Theor

    Dany Breslauer, Roberto Grossi, and Filippo Mignosi. Simple real-time constant-space string matching.Theor. Comput. Sci., 483:2–9, 2013.doi:10.1016/J.TCS.2012.11.040. 50

    work page doi:10.1016/j.tcs.2012.11.040 2013

  19. [20]

    Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat

    Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat. Ap- proximating text-to-pattern hamming distances. InProceedings of STOC 2020, page 643–656, 2020.doi:10.1145/3357713.3384266

    work page doi:10.1145/3357713.3384266 2020

  20. [21]

    Pissis, and Jakub Radoszewski

    Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski. Faster algorithms for longest common substring. InProc. of ESA, pages 30:1–30:17, 2021. doi:10.4230/LIPICS.ESA.2021.30

    work page doi:10.4230/lipics.esa.2021.30 2021

  21. [22]

    Pissis, Jakub Radoszewski, Wo- jciech Rytter, Juliusz Straszynski, Tomasz Walen, and Wiktor Zuba

    Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wo- jciech Rytter, Juliusz Straszynski, Tomasz Walen, and Wiktor Zuba. Circular pattern match- ing withkmismatches.J. Comput. Syst. Sci., 115:73–85, 2021.doi:10.1016/J.JCSS.2020. 07.003

    work page doi:10.1016/j.jcss.2020 2021

  22. [23]

    Language Model Cascades: Token-Level Uncertainty and Beyond

    Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Solon P. Pissis, Wo- jciech Rytter, Tomasz Walen, and Wiktor Zuba. Approximate circular pattern matching. InProc. of ESA, pages 35:1–35:19, 2022. Full version:https://doi.org/10.48550/arXiv. 2208.08915.doi:10.4230/LIPICS.ESA.2022.35

    work page internal anchor Pith review doi:10.48550/arxiv 2022

  23. [24]

    Counting distinct square substrings in sublinear time

    Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, and Wiktor Zuba. Counting distinct square substrings in sublinear time. InProc. of MFCS, pages 36:1–36:19, 2025.doi:10.4230/LIPICS.MFCS.2025.36

    work page doi:10.4230/lipics.mfcs.2025.36 2025

  24. [26]

    Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, and Wiktor Zuba

    Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, and Wiktor Zuba. Approximate circular pattern matching under edit distance. In Proc. of STACS, pages 24:1–24:22, 2024.doi:10.4230/LIPICS.STACS.2024.24

    work page doi:10.4230/lipics.stacs.2024.24 2024

  25. [27]

    Bit-Parallel Algorithms for Exact Circular String Matching.Comput

    Kuei-Hao Chen, Guan-Shieng Huang, and Richard Chia-Tung Lee. Bit-Parallel Algorithms for Exact Circular String Matching.Comput. J., 57(5):731–743, 03 2013.doi:10.1093/ comjnl/bxt023

    2013

  26. [28]

    Streaming and small space approximation algorithms for edit distance and longest common subsequence

    Kuan Cheng, Alireza Farhadi, MohammadTaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin, and Yu Zheng. Streaming and small space approximation algorithms for edit distance and longest common subsequence. InProc. of ICALP, pages 54:1–54:20, 2021.doi:10.4230/LIPICS.ICALP.2021.54

    work page doi:10.4230/lipics.icalp.2021.54 2021

  27. [29]

    A black box for online approximate pattern matching.Inf

    Raphaël Clifford, Klim Efremenko, Benny Porat, and Ely Porat. A black box for online approximate pattern matching.Inf. Comput., 209(4):731–736, 2011.doi:10.1016/J.IC. 2010.12.007

    work page doi:10.1016/j.ic 2011

  28. [30]

    Dictionary matching in a stream

    Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya. Dictionary matching in a stream. InProc. of ESA, pages 361–372, 2015.doi:10.1007/ 978-3-662-48350-3_31

    2015

  29. [31]

    (1971).Some Limit Theorems in Statistics.SIAM, Philadelphia

    Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya. The k-mismatch problem revisited. InProc. of SODA, pages 2039–2052, 2016.doi:10.1137/1. 9781611974331.ch142

    work page doi:10.1137/1 2039

  30. [32]

    The streaming k -mismatch problem

    Raphaël Clifford, Tomasz Kociumaka, and Ely Porat. The streaming k-mismatch problem. InProc. of SODA, pages 1106–1125, 2019.doi:10.1137/1.9781611975482.68. 51

    work page doi:10.1137/1.9781611975482.68 2019

  31. [33]

    The function-inversion problem: Barriers and opportunities

    Henry Corrigan-Gibbs and Dmitry Kogan. The function-inversion problem: Barriers and opportunities. InProc. of TCC (1), volume 11891, pages 393–421. Springer, 2019.doi: 10.1007/978-3-030-36030-6_16

    work page doi:10.1007/978-3-030-36030-6_16 2019

  32. [34]

    String-matching on ordered alphabets.Theor

    Maxime Crochemore. String-matching on ordered alphabets.Theor. Comput. Sci., 92(1):33– 47, 1992.doi:10.1016/0304-3975(92)90134-2

    work page doi:10.1016/0304-3975(92)90134-2 1992

  33. [35]

    Approximate string matching with gaps.Nordic J

    Maxime Crochemore, Costas Iliopoulos, Christos Makris, Wojciech Rytter, Athanasios Tsaka- lidis, and Kostas Tsichlas. Approximate string matching with gaps.Nordic J. of Computing, 9(1):54–65, March 2002

    2002

  34. [36]

    Non-uniform attacks against one-way functions and PRGs.Electron

    Anindya De, Luca Trevisan, and Madhur Tulsiani. Non-uniform attacks against one-way functions and PRGs.Electron. Colloquium Comput. Complex., TR09-113, 2009. URL:https: //eccc.weizmann.ac.il/report/2009/113

    2009

  35. [37]

    Genome compression: a novel approach for large collections.Bioinformatics, 29(20):2572–2578, 2013.doi:10.1093/ BIOINFORMATICS/BTT460

    Sebastian Deorowicz, Agnieszka Danek, and Szymon Grabowski. Genome compression: a novel approach for large collections.Bioinformatics, 29(20):2572–2578, 2013.doi:10.1093/ BIOINFORMATICS/BTT460

    2013

  36. [38]

    Robust relative compression of genomes with random access.Bioinformatics, 27(21):2979–2986, November 2011.doi:10.1093/ bioinformatics/btr505

    Sebastian Deorowicz and Szymon Grabowski. Robust relative compression of genomes with random access.Bioinformatics, 27(21):2979–2986, November 2011.doi:10.1093/ bioinformatics/btr505

    2011

  37. [39]

    Streaming regular expression membership and pattern matching

    Bartlomiej Dudek, Paweł Gawrychowski, Garance Gourdel, and Tatiana Starikovskaya. Streaming regular expression membership and pattern matching. InProc. of SODA, pages 670–694, 2022.doi:10.1137/1.9781611977073.30

    work page doi:10.1137/1.9781611977073.30 2022

  38. [40]

    Sublinear time Lempel-Ziv (LZ77) factorization

    Jonas Ellert. Sublinear time Lempel-Ziv (LZ77) factorization. InProc. of SPIRE, pages 171–187, 2023.doi:10.1007/978-3-031-43980-3_14

    work page doi:10.1007/978-3-031-43980-3_14 2023

  39. [41]

    Streaming periodicity with mismatches

    Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou. Streaming periodicity with mismatches. InProc. of APPROX-RANDOM, pages 42:1–42:21, 2017.doi:10.4230/ LIPICS.APPROX-RANDOM.2017.42

    2017

  40. [42]

    Periodicity in data streams with wildcards

    Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou. Periodicity in data streams with wildcards. InProc. of CSR, pages 90–105, 2018.doi:10.1007/ 978-3-319-90530-3_9

    2018

  41. [43]

    Periodicity in streams

    Funda Ergün, Hossein Jowhari, and Mert Saglam. Periodicity in streams. InProc. of APPROX-RANDOM, volume 6302, pages 545–559. Springer, 2010.doi:10.1007/ 978-3-642-15369-3_41

    2010

  42. [44]

    Rigorous time/space trade-offs for inverting functions.SIAM J

    Amos Fiat and Moni Naor. Rigorous time/space trade-offs for inverting functions.SIAM J. Comput., 29(3):790–803, 2000.doi:10.1137/S0097539795280512

    work page doi:10.1137/s0097539795280512 2000

  43. [45]

    Fine and Herbert S

    Nathan J. Fine and Herbert S. Wilf. Uniqueness theorems for periodic functions.Proc. Am. Math. Soc., 16:109–114, 1965.doi:10.1090/S0002-9939-1965-0174934-9

    work page doi:10.1090/s0002-9939-1965-0174934-9 1965

  44. [46]

    Approximat- ing LZ77 via small-space multiple-pattern matching

    Johannes Fischer, Travis Gagie, Paweł Gawrychowski, and Tomasz Kociumaka. Approximat- ing LZ77 via small-space multiple-pattern matching. InProc. of ESA, pages 533–544, 2015. Full version available at arXiv:1504.06647.doi:10.1007/978-3-662-48350-3_45. 52

    work page doi:10.1007/978-3-662-48350-3_45 2015

  45. [47]

    Streaming property testing of visibly pushdown languages

    Nathanaël François, Frédéric Magniez, Michel de Rougemont, and Olivier Serre. Streaming property testing of visibly pushdown languages. InProc. of ESA, pages 43:1–43:17, 2016. doi:10.4230/LIPICS.ESA.2016.43

    work page doi:10.4230/lipics.esa.2016.43 2016

  46. [48]

    Self-testing/correcting with applications to numerical problems.J

    Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees.J. Comput. Syst. Sci., 47(3):424–436, 1993.doi:10.1016/0022-0000(93) 90040-4

    work page doi:10.1016/0022-0000(93 1993

  47. [49]

    Efficient algorithms for pattern matching with general gaps, character classes, and transposition invariance.Inf

    Kimmo Fredriksson and Szymon Grabowski. Efficient algorithms for pattern matching with general gaps, character classes, and transposition invariance.Inf. Retr., 11(4):335–357, 2008. doi:10.1007/S10791-008-9054-Z

    work page doi:10.1007/s10791-008-9054-z 2008

  48. [50]

    Average-optimal string matching.J

    Kimmo Fredriksson and Szymon Grabowski. Average-optimal string matching.J. Discrete Algorithms, 7(4):579–594, 2009.doi:10.1016/j.jda.2008.09.001

    work page doi:10.1016/j.jda.2008.09.001 2009

  49. [51]

    Nested counters in bit-parallel string match- ing

    Kimmo Fredriksson and Szymon Grabowski. Nested counters in bit-parallel string match- ing. InProc. of LATA, volume 5457, pages 338–349. Springer, 2009.doi:10.1007/ 978-3-642-00982-2_29

    2009

  50. [52]

    Pissis, Jakub Radoszewski, Michelle Sweering, and Wiktor Zuba

    Estéban Gabory, Moses Njagi Mwaniki, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski, Michelle Sweering, and Wiktor Zuba. Elastic-degenerate string comparison.Inf. Comput., 304:105296, 2025.doi:10.1016/j.ic.2025.105296

    work page doi:10.1016/j.ic.2025.105296 2025

  51. [53]

    The cell probe complexity of succinct data structures

    Anna Gál and Peter Bro Miltersen. The cell probe complexity of succinct data structures. Theor. Comput. Sci., 379(3):405–417, 2007.doi:10.1016/J.TCS.2007.02.047

    work page doi:10.1016/j.tcs.2007.02.047 2007

  52. [54]

    Automata theory on sliding windows

    Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey, and Konstantinos Mamouras. Automata theory on sliding windows. InProc. of STACS, pages 31:1–31:14, 2018.doi: 10.4230/LIPIcs.STACS.2018.31

    work page doi:10.4230/lipics.stacs.2018.31 2018

  53. [55]

    Querying regular languages over sliding windows

    Moses Ganardi, Danny Hucke, and Markus Lohrey. Querying regular languages over sliding windows. InProc. of FSTTCS, pages 18:1–18:14, 2016.doi:10.4230/LIPIcs.FSTTCS.2016. 18

    work page doi:10.4230/lipics.fsttcs.2016 2016

  54. [56]

    URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs

    Moses Ganardi, Danny Hucke, and Markus Lohrey. Randomized sliding window algorithms for regular languages. InProc. of ICALP, pages 127:1–127:13, 2018.doi:10.4230/LIPIcs. ICALP.2018.127

    work page doi:10.4230/lipics 2018

  55. [57]

    Sliding window algorithms for regular languages

    Moses Ganardi, Danny Hucke, and Markus Lohrey. Sliding window algorithms for regular languages. InProc. of LATA, pages 26–35, 2018.doi:10.1007/978-3-319-77313-1_2

    work page doi:10.1007/978-3-319-77313-1_2 2018

  56. [58]

    Regular languages in the sliding window model.TheoretiCS, 4, 2025

    Moses Ganardi, Danny Hucke, Markus Lohrey, Konstantinos Mamouras, and Tatiana Starikovskaya. Regular languages in the sliding window model.TheoretiCS, 4, 2025. doi:10.46298/THEORETICS.25.8

    work page doi:10.46298/theoretics.25.8 2025

  57. [59]

    Sliding window property testing for regular languages

    Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya. Sliding window property testing for regular languages. InProc. of ISAAC, pages 6:1–6:13, 2019.doi: 10.4230/LIPIcs.ISAAC.2019.6

    work page doi:10.4230/lipics.isaac.2019.6 2019

  58. [60]

    Sliding windows over context-free languages

    Moses Ganardi, Artur Jeż, and Markus Lohrey. Sliding windows over context-free languages. InProc. of MFCS, pages 15:1–15:15, 2018.doi:10.4230/LIPIcs.MFCS.2018.15. 53

    work page doi:10.4230/lipics.mfcs.2018.15 2018

  59. [61]

    Pissis, and Karol Pokorski

    Paweł Gawrychowski, Adam Górkiewicz, Pola Marciniak, Solon P. Pissis, and Karol Pokorski. Faster Approximate Elastic-Degenerate String Matching - Part B. InProc. of CPM, pages 29:1–29:21, 2025.doi:10.4230/LIPIcs.CPM.2025.29

    work page doi:10.4230/lipics.cpm.2025.29 2025

  60. [62]

    Shur, and Przemyslaw Uznański

    Paweł Gawrychowski, Oleg Merkurev, Arseny M. Shur, and Przemyslaw Uznański. Tight tradeoffs for real-time approximation of longest palindromes in streams.Algorithmica, 81(9):3630–3654, 2019.doi:10.1007/s00453-019-00591-8

    work page doi:10.1007/s00453-019-00591-8 2019

  61. [63]

    Quasi-periodicity in streams

    Paweł Gawrychowski, Jakub Radoszewski, and Tatiana Starikovskaya. Quasi-periodicity in streams. InProc. of CPM, pages 22:1–22:14, 2019.doi:10.4230/LIPIcs.CPM.2019.22

    work page doi:10.4230/lipics.cpm.2019.22 2019

  62. [64]

    Streaming dictionary matching with mis- matches.Algorithmica, 84(4):896–916, 2022.doi:10.1007/S00453-021-00876-X

    Paweł Gawrychowski and Tatiana Starikovskaya. Streaming dictionary matching with mis- matches.Algorithmica, 84(4):896–916, 2022.doi:10.1007/S00453-021-00876-X

    work page doi:10.1007/s00453-021-00876-x 2022

  63. [65]

    Streaming periodicity with mismatches, wildcards, and edits

    Taha El Ghazi and Tatiana Starikovskaya. Streaming periodicity with mismatches, wildcards, and edits. InProc. of ISAAC, pages 36:1–36:20, 2025.doi:10.4230/LIPICS.ISAAC.2025.36

    work page doi:10.4230/lipics.isaac.2025.36 2025

  64. [66]

    The streaming k-mismatch problem: Tradeoffs between space and total time

    Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat. The streaming k-mismatch problem: Tradeoffs between space and total time. InProc. of CPM, pages 15:1–15:15, 2020. doi:10.4230/LIPIcs.CPM.2020.15

    work page doi:10.4230/lipics.cpm.2020.15 2020

  65. [67]

    Towardsoptimalapproximatestreamingpattern matching by matching multiple patterns in multiple streams

    ShayGolan, TsviKopelowitz, andElyPorat. Towardsoptimalapproximatestreamingpattern matching by matching multiple patterns in multiple streams. InProc. of ICALP, pages 65:1– 65:16, 2018.doi:10.4230/LIPIcs.ICALP.2018.65

    work page doi:10.4230/lipics.icalp.2018.65 2018

  66. [68]

    Streaming pattern matching with d wildcards.Algorithmica, 81(5):1988–2015, 2019

    Shay Golan, Tsvi Kopelowitz, and Ely Porat. Streaming pattern matching with d wildcards.Algorithmica, 81(5):1988–2015, 2019. URL:https://doi.org/10.1007/ s00453-018-0521-7,doi:10.1007/S00453-018-0521-7

    work page doi:10.1007/s00453-018-0521-7 1988

  67. [69]

    Real-time streaming multi-pattern search for constant alphabet

    Shay Golan and Ely Porat. Real-time streaming multi-pattern search for constant alphabet. InProc. of ESA, pages 41:1–41:15, 2017.doi:10.4230/LIPIcs.ESA.2017.41

    work page doi:10.4230/lipics.esa.2017.41 2017

  68. [70]

    On-Line Pattern Matching on Similar Texts

    RobertoGrossi, CostasS.Iliopoulos, ChangLiu, NadiaPisanti, SolonP.Pissis, AhmadRetha, Giovanna Rosone, Fatima Vayani, and Luca Versari. On-Line Pattern Matching on Similar Texts. InProc. of CPM, volume 78, pages 9:1–9:14, 2017.doi:10.4230/LIPIcs.CPM.2017.9

    work page doi:10.4230/lipics.cpm.2017.9 2017

  69. [71]

    Gusfield

    Dan Gusfield.Algorithms on Strings, Trees, and Sequences: Computer Science and Compu- tational Biology. Cambridge University Press, 1997.doi:10.1017/CBO9780511574931

    work page doi:10.1017/cbo9780511574931 1997

  70. [72]

    Haapasalo, P

    Tuukka Haapasalo, Panu Silvasti, Seppo Sippu, and Eljas Soisalon-Soininen. Online dic- tionary matching with variable-length gaps. InProc. of SEA, pages 76–87, 2011.doi: 10.1007/978-3-642-20662-7_7

    work page doi:10.1007/978-3-642-20662-7_7 2011

  71. [73]

    Thankachan

    Wing-Kai Hon, Tsung-Han Ku, Rahul Shah, and Sharma V. Thankachan. Space-efficient construction algorithm for the circular suffix tree. InProc. of CPM, pages 142–152, 2013. doi:10.1007/978-3-642-38905-4_15

    work page doi:10.1007/978-3-642-38905-4_15 2013

  72. [74]

    Thankachan

    Wing-Kai Hon, Chen-Hua Lu, Rahul Shah, and Sharma V. Thankachan. Succinct in- dexes for circular patterns. InProc. of ISAAC, pages 673–682, 2011.doi:10.1007/ 978-3-642-25591-5_69

    2011

  73. [75]

    Finding approximate occurrences of a pat- tern that contains gaps

    I.Lee, A.Apostolico, C.S.Iliopoulos, and K.Park. Finding approximate occurrences of a pat- tern that contains gaps. InProc. of AWOCA, pages 89—-100, 2003. 54

    2003

  74. [76]

    Iliopoulos, Ritu Kundu, and Solon P

    Costas S. Iliopoulos, Ritu Kundu, and Solon P. Pissis. Efficient pattern matching in elastic- degenerate strings.Inf. Comput., 279:104616, 2021.doi:10.1016/j.ic.2020.104616

    work page doi:10.1016/j.ic.2020.104616 2021

  75. [77]

    Iliopoulos, Solon P

    Costas S. Iliopoulos, Solon P. Pissis, and M. Sohel Rahman. Searching and indexing circular patterns. InAlgorithms for Next-Generation Sequencing Data: Techniques, Approaches, and Applications, pages 77–90. Springer, 2017.doi:10.1007/978-3-319-59826-0_3

    work page doi:10.1007/978-3-319-59826-0_3 2017

  76. [78]

    Karp and Michael O

    Richard M. Karp and Michael O. Rabin. Efficient randomized pattern-matching algorithms. IBM J. Res. Dev., 31(2):249–260, 1987.doi:10.1147/RD.312.0249

    work page doi:10.1147/rd.312.0249 1987

  77. [79]

    In: Proceedings of the 51st Annual ACM SIGACT Sympo- sium on Theory of Computing

    Dominik Kempa and Tomasz Kociumaka. String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure. InProc. of STOC, pages 756–767, 2019. doi:10.1145/3313276.3316368

    work page doi:10.1145/3313276.3316368 2019

  78. [80]

    Liu and Richard Peng and Aaron Sidford , editor =

    Dominik Kempa and Tomasz Kociumaka. Dynamic suffix array with polylogarithmic queries and updates. InProc. of STOC, pages 1657–1670, 2022.doi:10.1145/3519935.3520061

    work page doi:10.1145/3519935.3520061 2022

  79. [81]

    Breaking theO(n)-barrier in the construction of compressed suffix arrays and suffix trees

    Dominik Kempa and Tomasz Kociumaka. Breaking theO(n)-barrier in the construction of compressed suffix arrays and suffix trees. InProc. of SODA, pages 5122–5202, 2023. doi:10.1137/1.9781611977554.CH187

    work page doi:10.1137/1.9781611977554.ch187 2023

  80. [82]

    51 Shay Solomon, Amitai Uzrad, and Tianyi Zhang

    Dominik Kempa and Tomasz Kociumaka. Lempel-Ziv (LZ77) factorization in sublinear time. InProc. of FOCS, pages 2045–2055, 2024.doi:10.1109/FOCS61266.2024.00122

    work page doi:10.1109/focs61266.2024.00122 2045

Showing first 80 references.