Francis Zane

SODA Conference 2003 Conference Paper

Counting inversions in lists

• Anupam Gupta 0001
• Francis Zane

SODA Conference 2000 Conference Paper

Watermarking maps: hiding information in structured data

• Sanjeev Khanna
• Francis Zane

FOCS Conference 1998 Conference Paper

An Improved Exponential-Time Algorithm for k -SAT

• Ramamohan Paturi
• Pavel Pudlák
• Michael E. Saks
• Francis Zane

We propose and analyze a simple new algorithm for finding satisfying assignments of Boolean formulae in conjunctive normal form. The algorithm, ResolveSat, is a randomized variant of the DDL procedure by M. Davis et al. (1962) or Davis-Putnam procedure. Rather than applying the DLL procedure to the input formula F, however; ResolveSat enlarges F by adding additional clauses using limited resolution before performing DLL. The basic idea behind our analysis is the same as by R. Paturi (1997): a critical clause for a variable at a satisfying assignment gives rise to a unit clause in the DLL procedure with sufficiently high probability, thus increasing the probability of finding a satisfying assignment. In the current paper, we analyze the effect of multiple critical clauses (obtained through resolution) in producing unit clauses. We show that, for each k, the running time of ResolveSat on a k-CNF formula is significantly better than 2/sup n/, even in the worst case. In particular we show that the algorithm finds a satisfying assignment of a general 3-CNF in time O(2/sup. 446n/) with high probability; where the best previous algorithm has running time O(2/sup. 582n/). We obtain a better upper bound of O(2/sup (2ln2-1)/n+0(n))=O(2/sup 0. 387n/) for 3-CNF that have at most one satisfying assignment (unique k-SAT). For each k, the bounds for general k-CNF are the best known for the worst-case complexity of finding a satisfying solution for k-SAT, the idea of succinctly encoding satisfying solutions can be applied to obtain lower bounds on circuit site. Here, we exhibit a function f such that any depth-3 AND-OR circuit with bottom fan-in bounded by k requires /spl Omega/(2(c/sub k/n/k)) gates (with c/sub k/>1). This is the first such lower bound with c/sub k/>1.

FOCS Conference 1998 Conference Paper

Which Problems Have Strongly Exponential Complexity?

• Russell Impagliazzo
• Ramamohan Paturi
• Francis Zane

For several NP-complete problems, there have been a progression of better but still exponential algorithms. In this paper we address the relative likelihood of sub-exponential algorithms for these problems. We introduce a generalized reduction which we call sub-exponential reduction family (SERF) that preserves sub-exponential complexity. We show that Circuit-SAT is SERF-complete for all NP-search problems, and that for any fixed k, k-SAT, k-Colorability, k-Set Cover Independent Set, Clique, Vertex Cover are SERF-complete for the class SNP of search problems expressible by second order existential formulas whose first order part is universal. In particular, sub-exponential complexity for any one of the above problems implies the same for all others. We also look at the issue of proving strongly exponential lower bounds (that is, bounds of the form 2/sup /spl Omega/(n)/) for AC/sup 0/. This problem is even open far depth-3 circuits. In fact, such a bound for depth-3 circuits with even limited (at most n/sup /spl epsiv//) fan-infer bottom-level gates would imply a nonlinear size lower bound for logarithmic depth circuits. We show that with high probability even degree 2 random GF(2) polynomials require strongly exponential site for /spl Sigma//sub 3//sup k/ circuits for k=o(loglogn). We thus exhibit a much smaller space of 2(0(/sup n2/)) functions such that almost every function in this class requires strongly exponential size /spl Sigma//sub 3//sup k/ circuits. As a corollary, we derive a pseudorandom generator (requiring O(n/sup 2/) bits of advice) that maps n bits into a larger number of bits so that computing parity on the range is hard for /spl Sigma//sub 3//sup k/ circuits. Our main technical lemma is an algorithm that, for any fixed /spl epsiv/>0, represents an arbitrary k-CNF formula as a disjunction of 2/sup /spl epsiv/n/ k-CNF formulas that are sparse, e. g. , each having O(n) clauses.

STOC Conference 1997 Conference Paper

Exponential Lower Bounds for Depth 3 Boolean Circuits

• Ramamohan Paturi
• Michael E. Saks
• Francis Zane

FOCS Conference 1997 Conference Paper

Satisfiability Coding Lemma

• Ramamohan Paturi
• Pavel Pudlák
• Francis Zane

We present and analyze two simple algorithms for finding satisfying assignments of /spl kappa/-CNFs (Boolean formulae in conjunctive normal form with at most /spl kappa/ literals per clause). The first is a randomized algorithm which, with probability approaching 1, finds a satisfying assignment of a satisfiable /spl kappa/-CNF formula F in time O(n/sup 2/|F|2/sup n-n//spl kappa//). The second algorithm is deterministic, and its running time approaches 2/sup n-n/2/spl kappa// for large n and /spl kappa/. The randomized algorithm is the best known algorithm for /spl kappa/>3; the deterministic algorithm is the best known deterministic algorithm for /spl kappa/>4. We also show an /spl Omega/(n/sup 1/4/2/sup /spl radic/n/) lower bound on the size of depth 3 circuits of AND and OR gates computing the parity function. This bound is tight up to a constant factor. The key idea used in these upper and lower bounds is what we call the Satisfiability Coding Lemma. This basic lemma shows how to encode satisfying solutions of a /spl kappa/-CNF succinctly.