scientific article; zbMATH DE number 7650083
From MaRDI portal
Publication:5875468
DOI10.4230/LIPIcs.APPROX-RANDOM.2019.16MaRDI QIDQ5875468
Meng-Tsung Tsai, Martín Farach-Colton, Eric W. Allender
Publication date: 3 February 2023
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unique sequences containing no \(k\)-term arithmetic progressions
- Sequences containing no 3-term arithmetic progressions
- Finding large 3-free sets. I. The small \(n\) case
- On the complexity of constructing Golomb rulers
- A note on the independence number of triangle-free graphs
- Short propositional formulas represent nondeterministic computations
- A study on two geometric location problems
- The node-deletion problem for hereditary properties is NP-complete
- A dense infinite Sidon sequence
- On Turan's theorem for sparse graphs
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Computing independent sets in graphs with large girth
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Which problems have strongly exponential complexity?
- On a class of \(O(n^ 2)\) problems in computational geometry
- Subquadratic algorithms for algebraic 3SUM
- The Approximability of Constraint Satisfaction Problems
- On the Complexity of Some Common Geometric Location Problems
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Some Ramsey-Type Numbers and the Independence Ratio
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Applications of a Planar Separator Theorem
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Approximation algorithms for NP-complete problems on planar graphs
- Separators for sphere-packings and nearest neighbor graphs
- A new algorithm for Golomb ruler derivation and proof of the 19 mark ruler
- Threesomes, Degenerates, and Love Triangles
- Forbidden Configurations in Discrete Geometry
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
- Solving k-SUM using few linear queries
- POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
- ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
- Weighted Ham-Sandwich Cuts
- Fast approximation algorithms for the diameter and radius of sparse graphs
- On the complexity of \(k\)-SAT
This page was built for publication:
