Q4638059 (Q4638059): Difference between revisions

@@ Property / cites work @@
+Subtree Isomorphism Revisited
@@ Property / cites work: Subtree Isomorphism Revisited / rank @@
+Normal rank
@@ Property / cites work @@
+If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
+Normal rank
@@ Property / cites work @@
+Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
+Normal rank
@@ Property / cites work @@
+Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
+Normal rank
@@ Property / cites work @@
+Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
+Normal rank
@@ Property / cites work @@
+Consequences of Faster Alignment of Sequences
@@ Property / cites work: Consequences of Faster Alignment of Sequences / rank @@
+Normal rank
@@ Property / cites work @@
+Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
+Normal rank
@@ Property / cites work @@
+More Applications of the Polynomial Method to Algorithm Design
+Normal rank
@@ Property / cites work @@
+Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
+Normal rank
@@ Property / cites work @@
+On Hardness of Jumbled Indexing
@@ Property / cites work: On Hardness of Jumbled Indexing / rank @@
+Normal rank
@@ Property / cites work @@
+Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
+Normal rank
@@ Property / cites work @@
+\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
+Normal rank
@@ Property / cites work @@
+Sparse RNA folding: time and space efficient algorithms
+Normal rank
@@ Property / cites work @@
+Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
+Normal rank
@@ Property / cites work @@
+Oblivious string embeddings and edit distance approximations
+Normal rank
@@ Property / cites work @@
+Robust pcps of proximity, shorter pcps and applications to coding
+Normal rank
@@ Property / cites work @@
+Short PCPs with Polylog Query Complexity
@@ Property / cites work: Short PCPs with Polylog Query Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Short PCPs with Projection Queries
@@ Property / cites work: Short PCPs with Projection Queries / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating the best Nash Equilibrium in <i>n<sup>o</sup></i><sup>(log <i>n</i>)</sup>-time breaks the Exponential Time Hypothesis
+Normal rank
@@ Property / cites work @@
+Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
+Normal rank
@@ Property / cites work @@
+Q5368725
@@ Property / cites work: Q5368725 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Satisfiability of Small Depth Circuits
+Normal rank
@@ Property / cites work @@
+Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
+Normal rank
@@ Property / cites work @@
+Q5351927
@@ Property / cites work: Q5351927 / rank @@
+Normal rank
@@ Property / cites work @@
+Streaming algorithms for embedding and computing edit distance in the low distance regime
+Normal rank
@@ Property / cites work @@
+Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
+Normal rank
@@ Property / cites work @@
+Hardness of RNA Folding Problem With Four Symbols.
+Normal rank
@@ Property / cites work @@
+Model and Objective Separation with Conditional Lower Bounds
+Normal rank
@@ Property / cites work @@
+Better Approximation Algorithms for the Graph Diameter
+Normal rank
@@ Property / cites work @@
+Performance analysis of some simple heuristics for computing longest common subsequences
+Normal rank
@@ Property / cites work @@
+Q2747613
@@ Property / cites work: Q2747613 / rank @@
+Normal rank
@@ Property / cites work @@
+A fast and practical bit-vector algorithm for the longest common subsequence problem
+Normal rank
@@ Property / cites work @@
+On Problems as Hard as CNF-SAT
@@ Property / cites work: On Problems as Hard as CNF-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
+Normal rank
@@ Property / cites work @@
+Efficient learning algorithms yield circuit lower bounds
+Normal rank
@@ Property / cites work @@
+Speedup of RNA Pseudoknotted Secondary Structure Recurrence Computation with the Four-Russians Method
+Normal rank
@@ Property / cites work @@
+On a class of \(O(n^2)\) problems in computational geometry
+Normal rank
@@ Property / cites work @@
+Amplification and Derandomization without Slowdown
+Normal rank
@@ Property / cites work @@
+Algorithms on Strings, Trees and Sequences
@@ Property / cites work: Algorithms on Strings, Trees and Sequences / rank @@
+Normal rank
@@ Property / cites work @@
+Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
+Normal rank
@@ Property / cites work @@
+In search of an easy witness: Exponential time vs. probabilistic polynomial time.
+Normal rank
@@ Property / cites work @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Local Reductions
@@ Property / cites work: Local Reductions / rank @@
+Normal rank
@@ Property / cites work @@
+Derandomizing polynomial identity tests means proving circuit lower bounds
+Normal rank
@@ Property / cites work @@
+Turing machines that take advice
@@ Property / cites work: Turing machines that take advice / rank @@
+Normal rank
@@ Property / cites work @@
+Incremental String Comparison
@@ Property / cites work: Incremental String Comparison / rank @@
+Normal rank
@@ Property / cites work @@
+A faster algorithm computing string edit distances
+Normal rank
@@ Property / cites work @@
+Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
+Normal rank
@@ Property / cites work @@
+Low distortion embeddings for edit distance
@@ Property / cites work: Low distortion embeddings for edit distance / rank @@
+Normal rank
@@ Property / cites work @@
+Towards polynomial lower bounds for dynamic problems
+Normal rank
@@ Property / cites work @@
+Fast approximation algorithms for the diameter and radius of sparse graphs
+Normal rank
@@ Property / cites work @@
+Q4164821
@@ Property / cites work: Q4164821 / rank @@
+Normal rank
@@ Property / cites work @@
+Subcubic Equivalences Between Path, Matrix, and Triangle Problems
+Normal rank
@@ Property / cites work @@
+On the Power of Small-Depth Computation
@@ Property / cites work: On the Power of Small-Depth Computation / rank @@
+Normal rank
@@ Property / cites work @@
+Automata, Languages and Programming
@@ Property / cites work: Automata, Languages and Programming / rank @@
+Normal rank
@@ Property / cites work @@
+Improving Exhaustive Search Implies Superpolynomial Lower Bounds
+Normal rank
@@ Property / cites work @@
+Natural Proofs versus Derandomization
@@ Property / cites work: Natural Proofs versus Derandomization / rank @@
+Normal rank
@@ Property / cites work @@
+Q4589023
@@ Property / cites work: Q4589023 / rank @@
+Normal rank
@@ Property / cites work @@
+Nonuniform ACC Circuit Lower Bounds
@@ Property / cites work: Nonuniform ACC Circuit Lower Bounds / rank @@
+Normal rank
@@ Property / cites work @@
+Q5368736
@@ Property / cites work: Q5368736 / rank @@
+Normal rank