4 citations · 5 across the 2 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
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…
cs.CC2012★ 1 cited
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(…