1 citations · 1 across the 3 of their papers we have counts for
4 papers
The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
Nick Fischer, Marvin Künnemann, Mirza Redžić +1
Is detecting a -clique in -partite regular (hyper-)graphs as hard as in the general case? Intuition suggests yes, but proving this -- especially for hypergraphs -- poses nota…
The Effect of Sparsity on -Dominating Set and Related First-Order Graph Properties
Nick Fischer, Marvin Künnemann, Mirza Redzic
We revisit -Dominating Set, one of the first problems for which a tight conditional lower bound (for ), based on SETH, was shown (Pătraşcu and Williams, SODA…
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise
Marvin Künnemann, Bodo Manthey, Rianne Veenstra
The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of…
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem
Benjamin Doerr, Marvin Künnemann
The cryptogenography problem, introduced by Brody, Jakobsen, Scheder, and Winkler (ITCS 2014), is to collaboratively leak a piece of information known to only one member of a group…