No label defined (Q4638059)

From MaRDI portal

Revision as of 14:04, 15 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to:navigation, search

scientific article; zbMATH DE number 6866301

Language	Label	Description	Also known as
English	No label defined	scientific article; zbMATH DE number 6866301

Statements

scholarly article

0 references

0 references

Artūrs Bačkurs

0 references

publication date

3 May 2018

0 references

zbMATH Keywords

LCS

0 references

edit distance

0 references

hardness in P

0 references

describes a project that uses

0 references

0 references

MaRDI profile type

MaRDI publication profile

0 references

Subtree Isomorphism Revisited

0 references

If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser

0 references

Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter

0 references

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

0 references

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs

0 references

Consequences of Faster Alignment of Sequences

0 references

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture

0 references

More Applications of the Polynomial Method to Algorithm Design

0 references

Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions

0 references

On Hardness of Jumbled Indexing

0 references

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

0 references

\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs

0 references

Sparse RNA folding: time and space efficient algorithms

0 references

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

0 references

Oblivious string embeddings and edit distance approximations

0 references

Robust pcps of proximity, shorter pcps and applications to coding

0 references

Short PCPs with Polylog Query Complexity

0 references

Short PCPs with Projection Queries

0 references

Approximating the best Nash Equilibrium in <i>n<sup>o</sup></i><sup>(log <i>n</i>)</sup>-time breaks the Exponential Time Hypothesis

0 references

Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds

0 references

0 references

The Complexity of Satisfiability of Small Depth Circuits

0 references

Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility

0 references

0 references

Streaming algorithms for embedding and computing edit distance in the low distance regime

0 references

Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky

0 references

Hardness of RNA Folding Problem With Four Symbols.

0 references

Model and Objective Separation with Conditional Lower Bounds

0 references

Better Approximation Algorithms for the Graph Diameter

0 references

Performance analysis of some simple heuristics for computing longest common subsequences

0 references

0 references

A fast and practical bit-vector algorithm for the longest common subsequence problem

0 references

On Problems as Hard as CNF-SAT

0 references

On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter

0 references

Efficient learning algorithms yield circuit lower bounds

0 references

Speedup of RNA Pseudoknotted Secondary Structure Recurrence Computation with the Four-Russians Method

0 references

On a class of \(O(n^2)\) problems in computational geometry

0 references

Amplification and Derandomization without Slowdown

0 references

Algorithms on Strings, Trees and Sequences

0 references

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

0 references

In search of an easy witness: Exponential time vs. probabilistic polynomial time.

0 references

On the complexity of \(k\)-SAT

0 references

Which problems have strongly exponential complexity?

0 references

0 references

Local Reductions

0 references

Derandomizing polynomial identity tests means proving circuit lower bounds

0 references

Turing machines that take advice

0 references

Incremental String Comparison

0 references

A faster algorithm computing string edit distances

0 references

Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries

0 references

Low distortion embeddings for edit distance

0 references

Towards polynomial lower bounds for dynamic problems

0 references

Fast approximation algorithms for the diameter and radius of sparse graphs

0 references

0 references

Subcubic Equivalences Between Path, Matrix, and Triangle Problems

0 references

On the Power of Small-Depth Computation

0 references

Automata, Languages and Programming

0 references

Improving Exhaustive Search Implies Superpolynomial Lower Bounds

0 references

Natural Proofs versus Derandomization

0 references

0 references

Nonuniform ACC Circuit Lower Bounds

0 references

0 references

Identifiers

zbMATH Open document ID

0 references

10.4230/LIPIcs.ITCS.2017.11

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

zbMATH DE Number

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4638059

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q4638059&oldid=36389006"