More applications of the polynomial method to algorithm design

DOI10.1137/1.9781611973730.17MaRDI QIDQ5363029zbMATH OpenOpenAlexFDO

Authors Amir Abboud, Huacheng Yu, 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

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

Recommendations

• The polynomial method in circuit complexity applied to algorithm design (invited talk)
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• Faster all-pairs shortest paths via circuit complexity
• Faster Algebraic Algorithms for Path and Packing Problems
• From circuit complexity to faster all-pairs shortest paths

Cited in

(53)

• The fine-grained complexity of multi-dimensional ordering properties
• Fine-grained complexity theory: conditional lower bounds for computational geometry
• Dynamic and internal longest common substring
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• 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
• The polynomial method in circuit complexity applied to algorithm design (invited talk)
• Answering UCQs under updates and in the presence of integrity constraints
• 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
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• Towards hardness of approximation for polynomial time problems
• Tighter connections between Formula-SAT and shaving logs
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• From circuit complexity to faster all-pairs shortest paths
• Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
• Longest common substring made fully dynamic
• Classical algorithms from quantum and Arthur-Merlin communication protocols
• The Orthogonal Vectors Conjecture for Branching Programs and Formulas
• Sketching, streaming, and fine-grained complexity of (weighted) LCS
• Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• scientific article; zbMATH DE number 7561744 (Why is no real title available?)
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• scientific article; zbMATH DE number 7250154 (Why is no real title available?)
• Orthogonal vectors indexing
• Linear-time algorithm for long LCF with k mismatches
• scientific article; zbMATH DE number 7651219 (Why is no real title available?)
• Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• 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
• Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
• A robust version of Hegedűs's lemma, with applications
• Towards permissionless consensus in the standard model via fine-grained complexity
• Finer-grained reductions in fine-grained hardness of approximation
• Finer-grained reductions in fine-grained hardness of approximation
• A VLSI circuit model accounting for wire delay
• Partial permutations comparison, maintenance and applications
• The complexity of diameter on H-free graphs
• Computing generalized convolutions faster than brute force
• The complexity of diameter on \(H\)-free graphs
• Quantum algorithms for Hopcroft's problem
• Fine-grained hardness for edit distance to a fixed sequence
• Counting short vector pairs by inner product and relations to the permanent
• Longest common substring with gaps and related problems
• The planted orthogonal vectors problem
• Kronecker products, low-depth circuits, and matrix rigidity
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails

This page was built for publication: More applications of the polynomial method to algorithm design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363029)