On 3SUM-hard problems in the decision tree model

DOI10.1007/978-3-030-80049-9_16OpenAlexW3178116731MaRDI QIDQ2117780FDOQ2117780

Authors: Esther Ezra 

Publication date: 22 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-80049-9_16

Recommendations

• Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
• Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision tree model
• Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
• Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets.
• Subquadratic algorithms for algebraic generalizations of 3SUM

zbMATH Keywords

collinearity testing3SUM-hard problemsalgebraic decision tree modelsegment concurrency

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• On a class of \(O(n^ 2)\) problems in computational geometry
• Threesomes, degenerates, and love triangles
• On the Erdős distinct distances problem in the plane
• Lower bounds for linear degeneracy testing
• CUTTINGS AND APPLICATIONS
• On range searching with semialgebraic sets. II.
• Point location in arrangements of hyperplanes
• Better lower bounds on detecting affine and spherical degeneracies
• Title not available (Why is that?)
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• Incidence bounds for complex algebraic curves on Cartesian products
• Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets.
• Simplex Range Searching and Its Variants: A Review
• Solving \(k\)-SUM using few linear queries
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• Subquadratic algorithms for algebraic generalizations of 3SUM
• More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
• Near-optimal linear decision trees for k-SUM and related problems

Cited In (2)

• Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision tree model
• Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model

This page was built for publication: On 3SUM-hard problems in the decision tree model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117780)