121 citations · 142 across the 18 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.DS2011★ 121 cited
On Problems as Hard as CNFSAT
Marek Cygan, Holger Dell, Daniel Lokshtanov +6
The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for…
cs.CC2011★ 2 cited
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…