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^{\mathcal{O}(1)}$, and (d) a problem of computing a double 3-term arithmetic 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$ of magnitude $n^{\mathcal{O}(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].


翻译:我们证明了3SUM- 硬度( 没有强烈的次二次二次时间算法, 假设 3SUM猜想 ) 与在字符串中找到 Abelian 广场和添加性方方因数有关的数个问题 。 特别是, 我们得出了为找到此类因数而采用的最先进算法的有条件最佳性。 总的来说, 我们显示 3SUM- 硬度 (a) 检测到一个奇特半长的 Abel 方因数, (b) 所有 Abelian 方因数的计算中心, (c) 检测到一个在直径为 $+x_ 1, (d) 直径为x++j) 平方因数, (c) 在直径为 直径直的整数, (d) 在直径直值为 直径直的直值中, (c) 直径为直径直到直径直的平方位 。 (c) 直径直到直径直至直径直径直径直为平方列的平方列, (c) 直到直到直为直为直为直径直径直为直, 。 (c) 直为直为直为直为直为直为直为直为直, 直为直为直为直为直为直, 直为直为直为平方, 。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
三安光电到底发生了什么?
商业人物
7+阅读 · 2019年1月28日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年9月17日
VIP会员
Top
微信扫码咨询专知VIP会员