Radoszewski, Jakub ;
Rytter, Wojciech ;
Straszyński, Juliusz ;
Waleń, Tomasz ;
Zuba, Wiktor
Hardness of Detecting Abelian and Additive Square Factors in Strings
Abstract
We prove 3SUMhardness (no strongly subquadratictime 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 stateoftheart algorithms for finding such factors.
Overall, we show 3SUMhardness of (a) detecting an Abelian square factor of an odd halflength, (b) computing centers of all Abelian square factors, (c) detecting an additive square factor in a lengthn string of integers of magnitude n^{𝒪(1)}, and (d) a problem of computing a double 3term 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 Abeliansquarefree strings.
Our reductions also imply conditional lower bounds for detecting Abelian squares in strings over a constantsized alphabet. We also show a subquadratic upper bound in this case, applying a result of Chan and Lewenstein [STOC 2015].
BibTeX  Entry
@InProceedings{radoszewski_et_al:LIPIcs.ESA.2021.77,
author = {Radoszewski, Jakub and Rytter, Wojciech and Straszy\'{n}ski, Juliusz and Wale\'{n}, Tomasz and Zuba, Wiktor},
title = {{Hardness of Detecting Abelian and Additive Square Factors in Strings}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {77:177:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14658},
URN = {urn:nbn:de:0030drops146581},
doi = {10.4230/LIPIcs.ESA.2021.77},
annote = {Keywords: Abelian square, additive square, 3SUM problem}
}
31.08.2021
Keywords: 

Abelian square, additive square, 3SUM problem 
Seminar: 

29th Annual European Symposium on Algorithms (ESA 2021)

Issue date: 

2021 
Date of publication: 

31.08.2021 