Document Open Access Logo

Hardness of Detecting Abelian and Additive Square Factors in Strings

Authors Jakub Radoszewski , Wojciech Rytter , Juliusz Straszyński , Tomasz Waleń , Wiktor Zuba

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2021.77.pdf
  • Filesize: 0.98 MB
  • 19 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Pattern matching
Keywords
  • Abelian square
  • additive square
  • 3SUM problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We prove 3SUM-hardness (no strongly subquadratic-time algorithm, assuming the 3SUM conjecture) of several problems related to finding Abelian square and additive square factors in a string. In particular, we conclude conditional optimality of the state-of-the-art algorithms for finding such factors. 
Overall, we show 3SUM-hardness of (a) detecting an Abelian square factor of an odd half-length, (b) computing centers of all Abelian square factors, (c) detecting an additive square factor in a length-n string of integers of magnitude n^{𝒪(1)}, and (d) a problem of computing a double 3-term arithmetic progression (i.e., finding indices i ≠ j such that (x_i+x_j)/2 = x_{(i+j)/2}) in a sequence of integers x₁,… ,x_n of magnitude n^{𝒪(1)}.
Problem (d) is essentially a convolution version of the AVERAGE problem that was proposed in a manuscript of Erickson. We obtain a conditional lower bound for it with the aid of techniques recently developed by Dudek et al. [STOC 2020]. Problem (d) immediately reduces to problem (c) and is a step in reductions to problems (a) and (b). In conditional lower bounds for problems (a) and (b) we apply an encoding of Amir et al. [ICALP 2014] and extend it using several string gadgets that include arbitrarily long Abelian-square-free strings.
Our reductions also imply conditional lower bounds for detecting Abelian squares in strings over a constant-sized alphabet. We also show a subquadratic upper bound in this case, applying a result of Chan and Lewenstein [STOC 2015].

Cite As Get BibTex

Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba. Hardness of Detecting Abelian and Additive Square Factors in Strings. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 77:1-77:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.77

Author Details

Jakub Radoszewski
  • University of Warsaw, Poland
  • Samsung R&D, Warsaw, Poland
Wojciech Rytter
  • University of Warsaw, Poland
Juliusz Straszyński
  • University of Warsaw, Poland
Tomasz Waleń
  • University of Warsaw, Poland
Wiktor Zuba
  • University of Warsaw, Poland

Funding

  • Radoszewski, Jakub: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/03991.
  • Straszyński, Juliusz: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/03991.
  • Waleń, Tomasz: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/03991.
  • Zuba, Wiktor: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/03991.

Acknowledgements

The authors warmly thank Paweł Gawrychowski and Tomasz Kociumaka for helpful discussions.

References

  1. Peyman Afshani, Ingo van Duijn, Rasmus Killmann, and Jesper Sindahl Nielsen. A lower bound for jumbled indexing. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 592-606. SIAM, 2020. URL: http://dx.doi.org/10.1137/1.9781611975994.36.
  2. Amihood Amir, Alberto Apostolico, Tirza Hirst, Gad M. Landau, Noa Lewenstein, and Liat Rozenberg. Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings. Theoretical Computer Science, 656:146-159, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2016.04.030.
  3. Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 114-125. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_10.
  4. Hideo Bannai, Shunsuke Inenaga, and Dominik Köppl. Computing all distinct squares in linear time for integer alphabets. In Juha Kärkkäinen, Jakub Radoszewski, and Wojciech Rytter, editors, 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, July 4-6, 2017, Warsaw, Poland, volume 78 of LIPIcs, pages 22:1-22:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.CPM.2017.22.
  5. Ilya Baran, Erik D. Demaine, and Mihai Patrascu. Subquadratic algorithms for 3SUM. Algorithmica, 50(4):584-596, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9036-3.
  6. Felix Adalbert Behrend. On sets of integers which contain no three terms in arithmetical progression. Proceedings of the National Academy of Sciences of the United States of America, 32(12):331-332, 1946. URL: http://dx.doi.org/10.1073/pnas.32.12.331.
  7. Tom C. Brown and Allen R. Freedman. Arithmetic progressions in lacunary sets. Rocky Mountain Journal of Mathematics, 17(3):587-596, 1987. Google Scholar
  8. Tom C. Brown, Veselin Jungić, and Andrew Poelstra. On double 3-term arithmetic progressions. Integers, 14:A43, 2014. URL: https://www.emis.de/journals/INTEGERS/papers/o43/o43.Abstract.html.
  9. Julien Cassaigne, James D. Currie, Luke Schaeffer, and Jeffrey O. Shallit. Avoiding three consecutive blocks of the same size and same sum. Journal of the ACM, 61(2):10:1-10:17, 2014. URL: http://dx.doi.org/10.1145/2590775.
  10. Timothy M. Chan and Qizheng He. Reducing 3SUM to Convolution-3SUM. In Martin Farach-Colton and Inge Li Gørtz, editors, 3rd Symposium on Simplicity in Algorithms, SOSA@SODA 2020, Salt Lake City, UT, USA, January 6-7, 2020, pages 1-7. SIAM, 2020. URL: http://dx.doi.org/10.1137/1.9781611976014.1.
  11. Timothy M. Chan and Moshe Lewenstein. Clustered integer 3SUM via additive combinatorics. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 31-40. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746568.
  12. Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. Extracting powers and periods in a word from its runs structure. Theoretical Computer Science, 521:29-41, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2013.11.018.
  13. Larry J. Cummings and William F. Smyth. Weak repetitions in strings. Journal of Combinatorial Mathematics and Combinatorial Computing, 24:33-48, 1997. Google Scholar
  14. Bartłomiej Dudek, Paweł Gawrychowski, and Tatiana Starikovskaya. All non-trivial variants of 3-LDT are equivalent. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 974-981. ACM, 2020. URL: http://dx.doi.org/10.1145/3357713.3384275.
  15. Roger C. Entringer, Douglas E. Jackson, and J.A. Schatz. On nonrepetitive sequences. Journal of Combinatorial Theory, Series A, 16(2):159-164, 1974. URL: http://dx.doi.org/10.1016/0097-3165(74)90041-7.
  16. Paul Erdős. Some unsolved problems. Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 6:221-254, 1961. Google Scholar
  17. Jeff Erickson. Finding longest arithmetic progressions, 1999. URL: https://jeffe.cs.illinois.edu/pubs/arith.html.
  18. Aleksandr Andreevich Evdokimov. Strongly asymmetric sequences generated by a finite number of symbols. Doklady Akademii Nauk SSSR, 179(6):1268-1271, 1968. Google Scholar
  19. Gabriele Fici, Filippo Mignosi, and Jeffrey O. Shallit. Abelian-square-rich words. Theoretical Computer Science, 684:29-42, 2017. URL: http://dx.doi.org/10.1016/j.tcs.2017.02.012.
  20. Gabriele Fici and Aleksi Saarela. On the minimum number of abelian squares in a word. In Maxime Crochemore, James Currie, Gregory Kucherov, and Dirk Nowotka, editors, Combinatorics and Algorithmics of Strings (Dagstuhl Seminar 14111), volume 4 (3), pages 34-35, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/DagRep.4.3.28.
  21. Aviezri S. Fraenkel, Jamie Simpson, and Mike Paterson. On weak circular squares in binary words. In Alberto Apostolico and Jotun Hein, editors, Combinatorial Pattern Matching, 8th Annual Symposium, CPM 97, Aarhus, Denmark, June 30 - July 2, 1997, Proceedings, volume 1264 of Lecture Notes in Computer Science, pages 76-82. Springer, 1997. URL: http://dx.doi.org/10.1007/3-540-63220-4_51.
  22. Allen R. Freedman and Tom C. Brown. Sequences on sets of four numbers. Integers, 16:A33, 2016. URL: http://math.colgate.edu/~integers/q33/q33.Abstract.html.
  23. Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. How hard is it to find (honest) witnesses? In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 45:1-45:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.45.
  24. Dan Gusfield and Jens Stoye. Linear time algorithms for finding and representing all the tandem repeats in a string. Journal of Computer and System Sciences, 69(4):525-546, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2004.03.004.
  25. Lorenz Halbeisen and Norbert Hungerbühlre. An application of van der Waerden’s theorem in additive number theory. Integers, 0:A7, 2000. URL: http://math.colgate.edu/~integers/a7/a7.pdf.
  26. Veikko Keränen. A powerful abelian square-free substitution over 4 letters. Theoretical Computer Science, 410(38-40):3893-3900, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.05.027.
  27. Veikko Keränen. Abelian squares are avoidable on 4 letters. In Werner Kuich, editor, Automata, Languages and Programming, ICALP 1992, volume 623 of Lecture Notes in Computer Science, pages 41-52. Springer, 1992. URL: http://dx.doi.org/10.1007/3-540-55719-9_62.
  28. Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. Maximum number of distinct and nonequivalent nonstandard squares in a word. Theoretical Computer Science, 648:84-95, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2016.08.010.
  29. Tomasz Kociumaka, Jakub Radoszewski, and Bartłomiej Wiśniewski. Subquadratic-time algorithms for abelian stringology problems. In Ilias S. Kotsireas, Siegfried M. Rump, and Chee K. Yap, editors, Mathematical Aspects of Computer and Information Sciences - 6th International Conference, MACIS 2015, Berlin, Germany, November 11-13, 2015, Revised Selected Papers, volume 9582 of Lecture Notes in Computer Science, pages 320-334. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-32859-1_27.
  30. Tomasz Kociumaka, Jakub Radoszewski, and Bartłomiej Wiśniewski. Subquadratic-time algorithms for abelian stringology problems. AIMS Medical Science, 4(3):332-351, 2017. URL: http://dx.doi.org/10.3934/ms.2017.3.332.
  31. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1272-1287. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch89.
  32. Florian Lietard and Matthieu Rosenfeld. Avoidability of additive cubes over alphabets of four numbers. In Natasa Jonoska and Dmytro Savchuk, editors, Developments in Language Theory - 24th International Conference, DLT 2020, Tampa, FL, USA, May 11-15, 2020, Proceedings, volume 12086 of Lecture Notes in Computer Science, pages 192-206. Springer, 2020. URL: http://dx.doi.org/10.1007/978-3-030-48516-0_15.
  33. Giuseppe Pirillo and Stefano Varricchio. On uniformly repetitive semigroups. Semigroup Forum, 49:125-129, 1994. URL: http://dx.doi.org/10.1007/BF02573477.
  34. Peter A. B. Pleasants. Non-repetitive sequences. Mathematical Proceedings of the Cambridge Philosophical Society, 68:267-274, 1970. Google Scholar
  35. Mihai Pătrașcu. Towards polynomial lower bounds for dynamic problems. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 603-610. ACM, 2010. URL: http://dx.doi.org/10.1145/1806689.1806772.
  36. Michaël Rao and Matthieu Rosenfeld. Avoiding two consecutive blocks of same size and same sum over ℤ². SIAM Journal on Discrete Mathematics, 32(4):2381-2397, 2018. URL: http://dx.doi.org/10.1137/17M1149377.
  37. Lawrence Bruce Richmond and Jeffrey O. Shallit. Counting abelian squares. Electronic Journal of Combinatorics, 16(1), 2009. URL: http://www.combinatorics.org/Volume_16/Abstracts/v16i1r72.html.
  38. Raphaël Salem and Donald C. Spencer. On sets of integers which contain no three terms in arithmetical progression. Proceedings of the National Academy of Sciences of the United States of America, 28(12):561-563, 1942. URL: http://dx.doi.org/10.1073/pnas.28.12.561.
  39. Jamie Simpson. Solved and unsolved problems about abelian squares, 2018. URL: http://arxiv.org/abs/1802.04481.
  40. Shiho Sugimoto, Naoki Noda, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Computing abelian string regularities based on RLE. In Ljiljana Brankovic, Joe Ryan, and William F. Smyth, editors, Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Newcastle, NSW, Australia, July 17-21, 2017, Revised Selected Papers, volume 10765 of Lecture Notes in Computer Science, pages 420-431. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-78825-8_34.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact