More Applications of the Polynomial Method to Algorithm Design

DOI10.1137/1.9781611973730.17zbMath1372.68282OpenAlexW4241657494MaRDI QIDQ5363029

Amir Abboud, Huacheng Yu, R. Ryan Williams

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.17

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) General topics in the theory of algorithms (68W01)

Related Items (35)

Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis ⋮ Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Unnamed Item ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False) ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Longest common substring with approximately \(k\) mismatches ⋮ Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back ⋮ A new coding-based algorithm for finding closest pair of vectors ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Near-optimal quantum algorithms for string problems ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Computing generalized convolutions faster than brute force ⋮ Unnamed Item ⋮ Dynamic and internal longest common substring ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Longest common substring made fully dynamic ⋮ Unnamed Item ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ The Orthogonal Vectors Conjecture for Branching Programs and Formulas ⋮ Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Unnamed Item ⋮ The fine-grained complexity of multi-dimensional ordering properties ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Unnamed Item ⋮ Linear-Time Algorithm for Long LCF with k Mismatches ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry

This page was built for publication: More Applications of the Polynomial Method to Algorithm Design