On 3SUM-hard problems in the decision tree model
From MaRDI portal
Publication:2117780
DOI10.1007/978-3-030-80049-9_16OpenAlexW3178116731MaRDI QIDQ2117780
Publication date: 22 March 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-80049-9_16
Cites Work
- Unnamed Item
- Unnamed Item
- On the Erdős distinct distances problem in the plane
- Point location in arrangements of hyperplanes
- Better lower bounds on detecting affine and spherical degeneracies
- On a class of \(O(n^ 2)\) problems in computational geometry
- Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
- A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
- Incidence bounds for complex algebraic curves on Cartesian products
- A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
- Threesomes, Degenerates, and Love Triangles
- Simplex Range Searching and Its Variants: A Review
- Solving k-SUM using few linear queries
- CUTTINGS AND APPLICATIONS
- More Logarithmic-factor Speedups for 3SUM, (median,+)-convolution, and Some Geometric 3SUM-hard Problems
- Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
- Near-optimal linear decision trees for k-SUM and related problems
- On Range Searching with Semialgebraic Sets. II
- Lower bounds for linear degeneracy testing
- Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets.
This page was built for publication: On 3SUM-hard problems in the decision tree model