Subquadratic Algorithms for Algebraic 3SUM
Open Access
- 21 November 2018
- journal article
- research article
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 61 (4) , 698-734
Abstract
No abstract availableKeywords
Funding Information
- Action de Recherche Concertée (4.110.H.000023)
- Fulbright Association
- National Science Foundation (CNS-1229185, CCF-1319648)
- Fonds De La Recherche Scientifique - FNRS
- Fonds pour la Formation à la Recherche dans l’Industrie et dans l’Agriculture
- Israel Science Foundation (892/13)
This publication has 49 references indexed in Scilit:
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility2016
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture2015
- Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems2014
- On Hardness of Jumbled Indexing2014
- Necklaces, Convolutions, and X+YAlgorithmica, 2012
- All-Pairs Shortest Paths with Real Weights in O(n 3/log n) TimeAlgorithmica, 2007
- Subquadratic Algorithms for 3SUMAlgorithmica, 2007
- Lower bounds for linear degeneracy testingJournal of the ACM, 2005
- POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARDInternational Journal of Computational Geometry & Applications, 2001
- Product Range Spaces, Sensitive Sampling, and DerandomizationSIAM Journal on Computing, 1999