10 citations · 15 across the 7 of their papers we have counts for
5 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…
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…
Distributed PCP Theorems for Hardness of Approximation in P
Amir Abboud, Aviad Rubinstein, Ryan Williams
We present a new distributed model of probabilistically checkable proofs (PCP). A satisfying assignment to a CNF formula is shared between two parties, where…