scientific article; zbMATH DE number 7286914

DOI10.4086/toc.2020.v016a004zbMath1462.68067arXiv1802.02325OpenAlexW3090558544MaRDI QIDQ5140838

Lijie Chen

Publication date: 17 December 2020

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.02325

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

zbMATH Keywords

Chinese remainder theoremmaximum inner productSETHHopcroft's problemfine-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 (2)

Unnamed Item ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry

Uses Software

• FALCONN

Cites Work

• 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
• A (slightly) faster algorithm for Klee's measure problem
• Euclidean minimum spanning trees and bichromatic closest pairs
• Efficient partition trees
• A simple randomized sieve algorithm for the closest-pair problem
• 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
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Algebrization
• On the Complexity of Closest Pair via Polar-Pair of Point-Sets
• Faster Integer Multiplication
• 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
• Faster All-Pairs Shortest Paths via Circuit Complexity
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering
• Fast integer multiplication using generalized Fermat primes
• Conditional Lower Bounds for All-Pairs Max-Flow
• Exact and Approximate Maximum Inner Product Search with LEMP
• ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
• On the Parameterized Complexity of Approximating Dominating Set
• An Equivalence Class for Orthogonal Vectors
• Computational Complexity
• 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: