ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
From MaRDI portal
Publication:5122163
DOI10.1142/9789813272880_0188zbMath1490.68115OpenAlexW2972926935MaRDI QIDQ5122163
Publication date: 22 September 2020
Published in: Proceedings of the International Congress of Mathematicians (ICM 2018) (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/7659e4632203e8af7b4c3907b6c851e2ebc93496
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (28)
Equivalence classes and conditional hardness in massively parallel computations ⋮ On minimizing regular expressions without Kleene star ⋮ Geometric pattern matching reduces to \(k\)-SUM ⋮ Bisection of bounded treewidth graphs by convolutions ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions ⋮ Inapproximability of shortest paths on perfect matching polytopes ⋮ How fast can we play Tetris greedily with rectangular pieces? ⋮ Unnamed Item ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Computing generalized convolutions faster than brute force ⋮ Communication and information complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Algorithms and conditional lower bounds for planning problems ⋮ Geometric Pattern Matching Reduces to k-SUM. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sublinear-time reductions for big data computing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ Unnamed Item ⋮ Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry
This page was built for publication: ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
