121 citations · 142 across the 18 of their papers we have counts for
7 papers · 1 filter
Local Enumeration: The Not-All-Equal Case
Mohit Gurumukhani, Ramamohan Paturi, Michael Saks +1
Gurumukhani et al. (CCC'24) proposed the local enumeration problem Enum(k, t) as an approach to break the Super Strong Exponential Time Hypothesis (SSETH): for a natural number …
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…
Local Enumeration and Majority Lower Bounds
Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák +2
Depth-3 circuit lower bounds and -SAT algorithms are intimately related; the state-of-the-art -circuit lower bound and the -SAT algorithm are based on the same combina…
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…
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…
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(…
A Satisfiability Algorithm for AC
Russell Impagliazzo, William Matthews, Ramamohan Paturi
We consider the problem of efficiently enumerating the satisfying assignments to $\AC^0$ circuits. We give a zero-error randomized algorithm which takes an $\AC^0$ circuit as input…