28 citations · 52 across the 28 of their papers we have counts for
5 papers · 2 filters
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, Holger Dell +1
The Strong Exponential Time Hypothesis and the OV-conjecture are two popular hardness assumptions used to prove a plethora of lower bounds, especially in the realm of polynomial-ti…
Tighter Connections Between Formula-SAT and Shaving Logs
Amir Abboud, Karl Bringmann
A noticeable fraction of Algorithms papers in the last few decades improve the running time of well-known algorithms for fundamental problems by logarithmic factors. For example, t…
Multivariate Fine-Grained Complexity of Longest Common Subsequence
Karl Bringmann, Marvin Künnemann
We revisit the classic combinatorial pattern matching problem of finding a longest common subsequence (LCS). For strings and of length , a textbook algorithm solves LCS…
Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars
Karl Bringmann, Philip Wellnitz
Tree-adjoining grammars are a generalization of context-free grammars that are well suited to model human languages and are thus popular in computational linguistics. In the tree-a…
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve
Amir Abboud, Arturs Backurs, Karl Bringmann +1
Can we analyze data without decompressing it? As our data keeps growing, understanding the time complexity of problems on compressed inputs, rather than in convenient uncompressed…