48 citations · 61 across the 5 of their papers we have counts for
6 papers
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…
Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D
Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen +3
The -Means clustering problem on points is NP-Hard for any dimension , however, for the 1D case there exists exact polynomial time algorithms. Previous literature re…
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…
0-1 Integer Linear Programming with a Linear Number of Constraints
Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi +1
We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifi…
Satisfiability Algorithms for Restricted Circuit Classes
Stefan Schneider
In recent years, finding new satisfiability algorithms for various circuit classes has been a very active line of research. Despite considerable progress, we are still far away fro…
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits
Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider
We give a nontrivial algorithm for the satisfiability problem for cn-wire threshold circuits of depth two which is better than exhaustive search by a factor 2^{sn} where s= 1/c^{O(…