4 citations · 4 across the 2 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
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 -CNF formulas: How well can -CNF formulas capture threshold functions? Specifically, what is the largest number of assig…
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 da…