28 citations · 33 across the 10 of their papers we have counts for
7 papers · 1 filter
Impossibility Results for Grammar-Compressed Linear Algebra
Amir Abboud, Arturs Backurs, Karl Bringmann +1
To handle vast amounts of data, it is natural and popular to compress vectors and matrices. When we compress a vector from size down to size , it certainly makes it ea…
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…