scientific article; zbMATH DE number 7250154

DOI10.4230/LIPIcs.CCC.2018.14zbMath1441.68068MaRDI QIDQ5121902

Lijie Chen

Publication date: 22 September 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Chinese remainder theoremmaximum inner productSETHHopcroft's problemfined-grained complexityhardness of approximation in P

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (7)

Unnamed Item ⋮ Unnamed Item ⋮ On closest pair in Euclidean metric: monochromatic is as hard as bichromatic ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

Uses Software

• FALCONN
• LEMP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Even faster integer multiplication
• Probabilistic communication complexity
• Boolean function complexity. Advances and frontiers.
• Range searching with efficient hierarchical cuttings
• Euclidean minimum spanning trees and bichromatic closest pairs
• Efficient partition trees
• A simple randomized sieve algorithm for the closest-pair problem
• Conditional lower bounds for space/time tradeoffs
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem
• Towards polynomial lower bounds for dynamic problems
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Optimal Data-Dependent Hashing for Approximate Near Neighbors
• Algebrization
• Faster Integer Multiplication
• A (slightly) faster algorithm for klee's measure problem
• The Complexity of Satisfiability of Small Depth Circuits
• Rapid Multiplication of Rectangular Matrices
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• Higher Lower Bounds from the 3SUM Conjecture
• A Faster Subquadratic Algorithm for Finding Outlier Correlations
• A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering
• Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications
• Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
• Exact and Approximate Maximum Inner Product Search with LEMP
• ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
• Consequences of Faster Alignment of Sequences
• Faster all-pairs shortest paths via circuit complexity
• Computational Complexity
• More Applications of the Polynomial Method to Algorithm Design
• Beyond Locality-Sensitive Hashing
• Finding orthogonal vectors in discrete structures
• Fast approximation algorithms for the diameter and radius of sparse graphs
• On the complexity of \(k\)-SAT

This page was built for publication: