Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds (Q4993300): Difference between revisions

Latest revision as of 10:22, 30 July 2024

scientific article; zbMATH DE number 7359372

Language	Label	Description	Also known as
English	Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds	scientific article; zbMATH DE number 7359372

Statements

0 references

0 references

0 references

15 June 2021

0 references

zbMATH Keywords

distributed PCP

0 references

longest common subsequence

0 references

fine-grained complexity

0 references

circuit lower bounds

0 references

strong exponential time hypothesis

0 references

describes a project that uses

PSI-BLAST

0 references

BLAST

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Algebrization

0 references

Q4638059

0 references

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

0 references

Consequences of Faster Alignment of Sequences

0 references

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

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

Interactive Oracle Proofs

0 references

Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity

0 references

Short PCPs with Projection Queries

0 references

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

0 references

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

0 references

Performance analysis of some simple heuristics for computing longest common subsequences

0 references

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

0 references

The PCP theorem by gap amplification

0 references

Q3549691

0 references

Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography

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

Local Reductions

0 references

Interactive PCP

0 references

Incremental String Comparison

0 references

Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph

0 references

Q5111409

0 references

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

0 references

Low distortion embeddings for edit distance

0 references

Q5417690

0 references

Constant-round interactive proofs for delegating computation

0 references

Q4164821

0 references

A new algorithm for optimal 2-constraint satisfaction and its implications

0 references

Improving Exhaustive Search Implies Superpolynomial Lower Bounds

0 references

full work available at URL

https://doi.org/10.4230/LIPIcs.ITCS.2018.35

0 references

title

Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds (English)

0 references

Identifiers

zbMATH Open document ID

1462.68239

0 references

DOI

10.4230/LIPIcs.ITCS.2018.35

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4993300

@@ label / en / label / en @@
+Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
@@ Property / describes a project that uses @@
+PSI-BLAST
@@ Property / describes a project that uses: PSI-BLAST / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+BLAST
@@ Property / describes a project that uses: BLAST / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Algebrization
@@ Property / cites work: Algebrization / rank @@
+Normal rank
@@ Property / cites work @@
+Q4638059
@@ Property / cites work: Q4638059 / rank @@
+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 @@
+Consequences of Faster Alignment of Sequences
@@ Property / cites work: Consequences of Faster Alignment of Sequences / rank @@
+Normal rank
@@ Property / cites work @@
+Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
+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 @@
+Interactive Oracle Proofs
@@ Property / cites work: Interactive Oracle Proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
+Normal rank
@@ Property / cites work @@
+Short PCPs with Projection Queries
@@ Property / cites work: Short PCPs with Projection Queries / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
+Normal rank
@@ Property / cites work @@
+Streaming algorithms for embedding and computing edit distance in the low distance regime
+Normal rank
@@ Property / cites work @@
+Performance analysis of some simple heuristics for computing longest common subsequences
+Normal rank
@@ Property / cites work @@
+A fast and practical bit-vector algorithm for the longest common subsequence problem
+Normal rank
@@ Property / cites work @@
+The PCP theorem by gap amplification
@@ Property / cites work: The PCP theorem by gap amplification / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549691
@@ Property / cites work: Q3549691 / rank @@
+Normal rank
@@ Property / cites work @@
+Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography
+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 @@
+Local Reductions
@@ Property / cites work: Local Reductions / rank @@
+Normal rank
@@ Property / cites work @@
+Interactive PCP
@@ Property / cites work: Interactive PCP / rank @@
+Normal rank
@@ Property / cites work @@
+Incremental String Comparison
@@ Property / cites work: Incremental String Comparison / rank @@
+Normal rank
@@ Property / cites work @@
+Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
+Normal rank
@@ Property / cites work @@
+Q5111409
@@ Property / cites work: Q5111409 / rank @@
+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 @@
+Q5417690
@@ Property / cites work: Q5417690 / rank @@
+Normal rank
@@ Property / cites work @@
+Constant-round interactive proofs for delegating computation
+Normal rank
@@ Property / cites work @@
+Q4164821
@@ Property / cites work: Q4164821 / rank @@
+Normal rank
@@ Property / cites work @@
+A new algorithm for optimal 2-constraint satisfaction and its implications
+Normal rank
@@ Property / cites work @@
+Improving Exhaustive Search Implies Superpolynomial Lower Bounds
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.4230/LIPIcs.ITCS.2018.35
+Normal rank
@@ Property / OpenAlex ID @@
+W2782583418
@@ Property / OpenAlex ID: W2782583418 / rank @@
+Normal rank
@@ Property / title @@
+Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds (English)
+Normal rank