44 citations · 115 across the 13 of their papers we have counts for
8 papers · 1 filter
The Time Complexity of Fully Sparse Matrix Multiplication
Amir Abboud, Karl Bringmann, Nick Fischer +1
What is the time complexity of matrix multiplication of sparse integer matrices with nonzeros in the input and nonzeros in the output? This paper provides improv…
A Structural Investigation of the Approximability of Polynomial-Time Problems
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We initiate the systematic study of a recently introduced polynomial-time analogue of MaxSNP, which includes a large number of well-studied problems (including Nearest and Furthest…
Fine-Grained Completeness for Optimization in P
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime. Inspired by the first completeness results for dec…
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Karl Bringmann, Marvin Künnemann, Karol Węgrzycki
Zwick's -approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time , where i…
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability
Karl Bringmann, Marvin Künnemann, André Nusser
The discrete Fréchet distance is a popular measure for comparing polygonal curves. An important variant is the discrete Fréchet distance under translation, which enables detection…
Subquadratic Algorithms for Succinct Stable Matching
Marvin Künnemann, Daniel Moeller, Ramamohan Paturi +1
We consider the stable matching problem when the preference lists are not given explicitly but are represented in a succinct way and ask whether the problem becomes computationally…
Quasirandom Rumor Spreading: An Experimental Analysis
Benjamin Doerr, Tobias Friedrich, Marvin Künnemann +1
We empirically analyze two versions of the well-known "randomized rumor spreading" protocol to disseminate a piece of information in networks. In the classical model, in each round…
Randomized Rounding for Routing and Covering Problems: Experiments and Improvements
Benjamin Doerr, Marvin Künnemann, Magnus Wahlström
Following previous theoretical work by Srinivasan (FOCS 2001) and the first author (STACS 2006) and a first experimental evaluation on random instances (ALENEX 2009), we investigat…