Marvin Künnemann

activity

20172024

most citedOn the Fine-grained Complexity of One-Dimensional Dynamic Programming

4 citations · 4 across the 2 of their papers we have counts for

collaborators

3 papers

cs.CC2024

On Extremal Properties of k-CNF: Capturing Threshold Functions

Mohit Gurumukhani, Marvin Künnemann, Ramamohan Paturi

We consider a basic question on the expressiveness of $k$ -CNF formulas: How well can $k$ -CNF formulas capture threshold functions? Specifically, what is the largest number of assig…

cs.CG2023

Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions $d \geq 4$

Egor Gorbachev, Marvin Künnemann

Klee's measure problem (computing the volume of the union of $n$ axis-parallel boxes in $R^{d}$ ) is well known to have $n^{\frac{d}{2} \pm o (1)}$ -time algorithms (Overmars, Y…

cs.CC2017★ 4 cited

On the Fine-grained Complexity of One-Dimensional Dynamic Programming

Marvin Künnemann, Ramamohan Paturi, Stefan Schneider

In this paper, we investigate the complexity of one-dimensional dynamic programming, or more specifically, of the Least-Weight Subsequence (LWS) problem: Given a sequence of $n$ da…

On Extremal Properties of k-CNF: Capturing Threshold Functions

Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d≥4

On the Fine-grained Complexity of One-Dimensional Dynamic Programming

Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions $d \geq 4$