×

Improved subquadratic 3SUM. (English) Zbl 1359.68130

Summary: In the 3SUM problem we are given three lists \(\mathcal {A}\), \(\mathcal {B}\), \(\mathcal {C}\), of \(n\) real numbers, and are asked to find \((a,b,c)\in \mathcal {A}\times \mathcal {B}\times \mathcal {C}\) such that \(a+b=c\). The longstanding 3SUM conjecture – that 3SUM could not be solved in subquadratic time – was recently refuted by A. Grønlund and S. Pettie [“Threesomes, degenerates, and love triangles”, in: Proceedings of the 55th annual IEEE symposium on foundations of computer science, FOCS’14. Los Alamitos, CA: IEEE Computer Society. 621–630 (2014; doi:10.1109/FOCS.2014.72)]. They presented \(O\left( n^2(\log \log n)^{\alpha }/(\log n)^{\beta }\right) \) algorithms for 3SUM and for the related problems Convolution3SUM and ZeroTriangle, where \(\alpha \) and \(\beta \) are constants that depend on the problem and whether the algorithm is deterministic or randomized (and for ZeroTriangle the main factor is \(n^3\) rather than \(n^2\)). We simplify Grønlund and Pettie’s algorithms and obtain better bounds, namely, \(\alpha =\beta =1\), deterministically. For 3SUM our bound is better than both the deterministic and the randomized bounds of Grønlund and Pettie [loc. cit.]. For the other problems our bounds are better than their deterministic bounds, and match their randomized bounds.

MSC:

68Q25 Analysis of algorithms and problem complexity
68W05 Nonnumerical algorithms
68W20 Randomized algorithms
Full Text: DOI

References:

[1] Ailon, N., Chazelle, B.: Lower bounds for linear degeneracy testing. J. ACM 52(2), 157-171 (2005) · Zbl 1286.68172 · doi:10.1145/1059513.1059515
[2] Baran, I., Demaine, E.D., Pǎtraşcu, M.: Subquadratic algorithms for 3SUM. Algorithmica 50(4), 584-596 (2008) · Zbl 1147.68861 · doi:10.1007/s00453-007-9036-3
[3] Butman, A., Clifford, P., Clifford, R., Jalsenius, M., Lewenstein, N., Porat, B., Porat, E., Sach, B.: Pattern matching under polynomial transformation. SIAM J. Comput. 42(2), 611-633 (2013) · Zbl 1271.68248 · doi:10.1137/110853327
[4] Chan, T.M.: All-pairs shortest paths with real weights in \[\text{ O }(n^3/\log n)O\](n3/logn) time. Algorithmica 50(2), 236-243 (2008) · Zbl 1151.68043 · doi:10.1007/s00453-007-9062-1
[5] Chan, T.M.: Speeding up the four Russians algorithm by about one more logarithmic factor. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 212-217. Society for Industrial and Applied Mathematics, Philadelphia (2015) · Zbl 1372.68284
[6] Erickson, J.: Lower bounds for linear satisfiability problems. Chic. J. Theor. Comput. Sci. 8, 388-395 (1997) · Zbl 0849.68041
[7] Gajentaan, A., Overmars, M.H.: On a class of \[\text{ O }(n^2)O\](n2) problems in computational geometry. Comput. Geom. 5(3), 165-185 (1995) · Zbl 0839.68105 · doi:10.1016/0925-7721(95)00022-2
[8] Grønlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. In: Proceedings of the 55th IEEE Symposium on Foundations of Computer Science. ArXiv preprint arXiv:1404.0799 (2014) · Zbl 1422.68112
[9] Impagliazzo, R., Lovett, S., Paturi, R., Schneider, S.: 0-1 Integer linear programming with a linear number of constraints. ArXiv preprint arXiv:1401.5512 (2014) · Zbl 0849.68041
[10] Pǎtraşcu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 603-610. Association for Computing Machinery, New York (2010) · Zbl 1293.68153
[11] Preparata, F.P., Shamos, M.I.: Computational Geometry, an Introduction. Springer, New York (1985) · Zbl 0575.68059 · doi:10.1007/978-1-4612-1098-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.