Propositional Satisfiability (SAT) was one of the first problems to be
proven NP-complete. Though the question of P=NP? has not yet been settled,
it is widely believed that P!=NP. Therefore, current research on SAT is
focused on finding non-trivial exponential upper bounds for SAT
algorithms. For example, an algorithm running in $ O(2^{n/r})$, for
instance, with large $r$ could prove useful in solving many practical
problems.

In this talk, we introduce and motivate k-CNF SAT, and discuss some recent
work (done in collaboration with Ravi Gummadi and N.S. Narayanaswamy):

An independent set of variables is one in which no two variables occur in
the same clause in a given instance of $k$-SAT. Instances of $k$-SAT with
an independent set of size $i$ can be solved in time, within a polynomial
factor of $O(2^{n-i})$. In this paper, we present an algorithm for $k$-SAT
based on a modification of the Satisfiability Coding Lemma. Our algorithm
runs with in a polynomial factor of $2^{(n-i)(1-\frac{1}{2k-2})}$, where
$i$ is the size of an independent set. We also present a variant of
Sch\"{o}ning's randomized local-search algorithm for $k$-SAT that runs in
time which is with in a polynomial factor of $(\frac{2k-3}{k-1})^{n-i}$.

The paper is available at http://www.cise.ufl.edu/~vr1/sat2004_lncs.pdf