English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We prove 3SUM-hardness (no strongly subquadratic-time algorithm, assuming the3SUM conjecture) of several problems related to finding Abelian square andadditive square factors in a string. In particular, we conclude conditionaloptimality of the state-of-the-art algorithms for finding such factors.  Overall, we show 3SUM-hardness of (a) detecting an Abelian square factor ofan odd half-length, (b) computing centers of all Abelian square factors, (c)detecting an additive square factor in a length-$n$ string of integers ofmagnitude $n^{\mathcal{O}(1)}$, and (d) a problem of computing a double 3-termarithmetic progression (i.e., finding indices $i \ne j$ such that$(x_i+x_j)/2=x_{(i+j)/2}$) in a sequence of integers $x_1,\dots,x_n$ ofmagnitude $n^{\mathcal{O}(1)}$.  Problem (d) is essentially a convolution version of the AVERAGE problem thatwas proposed in a manuscript of Erickson. We obtain a conditional lower boundfor it with the aid of techniques recently developed by Dudek et al. [STOC2020]. Problem (d) immediately reduces to problem (c) and is a step inreductions 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 itusing several string gadgets that include arbitrarily long Abelian-square-freestrings.  Our reductions also imply conditional lower bounds for detecting Abeliansquares in strings over a constant-sized alphabet. We also show a subquadraticupper bound in this case, applying a result of Chan and Lewenstein [STOC 2015].

Hardness of Detecting Abelian and Additive Square Factors in Strings