scientific article; zbMATH DE number 7375935
From MaRDI portal
Publication:5002674
DOI10.4230/LIPIcs.ICALP.2018.8zbMath1499.68137arXiv1804.08978MaRDI QIDQ5002674
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1804.08978
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
A Linear-Time n 0.4 -Approximation for Longest Common Subsequence, Unnamed Item, A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem, Unnamed Item, Unnamed Item, Algorithms and lower bounds for de morgan formulas of low-communication leaf gates, Fine-grained complexity theory: conditional lower bounds for computational geometry, A \#SAT algorithm for small constant-depth circuits with PTF gates
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- Approximating the Fréchet distance for realistic curves in near linear time
- Fréchet distance with speed limits
- Can we compute the similarity between surfaces?
- Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
- A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
- A faster algorithm computing string edit distances
- Size-depth tradeoffs for Boolean formulae
- A fast and practical bit-vector algorithm for the longest common subsequence problem
- An improved combinatorial algorithm for Boolean matrix multiplication
- Comparison of distance measures for planar curves
- A bit-string longest-common-subsequence algorithm
- Mining circuit lower bound proofs for meta-algorithms
- Fast and compact regular expression matching
- Subquadratic algorithms for succinct stable matching
- Subquadratic algorithms for 3SUM
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Satisfiability on Mixed Instances
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases
- DETECTING COMMUTING PATTERNS BY CLUSTERING SUBTRAJECTORIES
- Geodesic Fréchet distance inside a simple polygon
- Nonuniform ACC Circuit Lower Bounds
- Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits
- An improved exponential-time algorithm for k -SAT
- Faster Regular Expression Matching
- The Complexity of Satisfiability of Small Depth Circuits
- On Time Versus Space
- A Four Russians algorithm for regular expression pattern matching
- The Shrinkage Exponent of de Morgan Formulas is 2
- The String-to-String Correction Problem
- A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
- Approximate nearest neighbor algorithms for Frechet distance via product metrics
- New Bounds for Approximating Extremal Distances in Undirected Graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Subtree Isomorphism Revisited
- Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework
- The effect of random restrictions on formula size
- Shrinkage of de Morgan formulae under restriction
- Consequences of Faster Alignment of Sequences
- Regularity Lemmas and Combinatorial Algorithms
- Faster all-pairs shortest paths via circuit complexity
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- More Applications of the Polynomial Method to Algorithm Design
- Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
- Four Soviets Walk the Dog—with an Application to Alt's Conjecture
- Jaywalking Your Dog: Computing the Fréchet Distance with Shortcuts
- Fréchet Distance for Curves, Revisited
- Computing the Discrete Fréchet Distance in Subquadratic Time
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Programming Techniques: Regular expression search algorithm
- On the complexity of \(k\)-SAT
