scientific article; zbMATH DE number 6866301

DOI10.4230/LIPIcs.ITCS.2017.11zbMath1402.68068MaRDI QIDQ4638059

Publication date: 3 May 2018

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

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (6)

Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence ⋮ Unnamed Item ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ Unnamed Item ⋮ Unnamed Item

Uses Software

PSI-BLAST
BLAST

Cites Work

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

This page was built for publication: