Karl Bringmann

2 accepted papers

2020

Impossibility Results for Grammar-Compressed Linear Algebra

Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann

NeurIPS 2020poster

To handle vast amounts of data, it is natural and popular to compress vectors and matrices. When we compress a vector from size N down to size n << N, it certainly makes it easier to store and transmit efficiently, but does it also make it easier to process?

Cited by 15 Source ↗PDF ↗Scholar ↗

2017

Approximation Algorithms for $\ell_0$-Low Rank Approximation

Karl Bringmann, Pavel Kolev, David Woodruff

NeurIPS 2017poster

We study the $\ell_0$-Low Rank Approximation Problem, where the goal is, given an $m \times n$ matrix $A$, to output a rank-$k$ matrix $A'$ for which $\|A'-A\|_0$ is minimized. Here, for a matrix $B$, $\|B\|_0$ denotes the number of its non-zero entries. This NP-hard variant of low rank a…

Cited by 19 Source ↗PDF ↗Scholar ↗