Abstracts

Witnesses for non-satisfiability of dense random 3CNF formulas: We consider random 3CNF formulas with n variables and m clauses. It is well known that when m > cn (for a sufficiently large constant c ), most formulas are not satisfiable. However, it is not known whether such formulas are likely to have polynomial size witnesses that certify that they are not satisfiable. A value of m &cong n 3/2 was the forefront of our knowledge in this respect. When m > cn 3/2 , such witnesses are known to exist, based on spectral techniques. When m < n 3/2 - &epsilon , it is known that resolution (which is a common approach for refutation) cannot produce witnesses of size smaller than 2 n &epsilon . Likewise, it is known that certain variants of the spectral techniques do not work in this range. In the current paper we show that when m > cn 7/5 , almost all 3CNF formulas have polynomial size witnesses for non-satisfiability. We also show that such a witness can be found in time 2 O(n 0.2 log n) , whenever it exists. Our approach is based on an extension of the known spectral techniques, and involves analyzing a certain fractional packing problem for random 3-uniform hypergraphs.

Random 3CNF formulas elude the Lovasz theta function: Let φ be a 3CNF formula with n variables and m clauses. A simple nonconstructive argument shows that when m is sufficiently large compared to n , most 3CNF formulas are not satisfiable. It is an open question whether there is an efficient refutation algorithm that for most such formulas proves that they are not satisfiable. A possible approach to refute a formula φ is: first, translate it into a graph Gφ using a generic reduction from 3-SAT to max-IS, then bound the maximum independent set of Gφ using the Lovasz theta function. If the theta function returns a value < m , this is a certificate for the unsatisfiability of φ . We show that for random formulas with m < n3/2 -o(1) clauses, the above approach fails, i.e. the theta function is likely to return a value of m .

On the expansion of the giant component in percolated (n,d,λ) graphs: Let d > d0 be a sufficiently large constant. A (n,d,c√d) graph G is a d-regular graph over n vertices whose second largest (in absolute value) eigenvalue is at most c√d . For any 0 < p < 1, Gp is the graph induced by retaining each edge of G with probability p. It is known that for p > 1/d the graph Gp almost surely contains a unique giant component (a connected component with linear number vertices). We show that for p > 5c/√d the giant component of Gp almost surely has an edge expansion of at least 1/log2n .

Finding a maximum independent set in a sparse random graph: We consider the problem of finding a maximum independent set in a random graph. The random graph G is modelled as follows. Every edge is included independently with probability d/n, where d is some sufficiently large constant. Thereafter, for some constant α, a subset I of αn vertices is chosen at random, and all edges within this subset are removed. In this model, the planted independent set I is a good approximation for the maximum independent set Imax , but both I \ Imax and Imax \ I are likely to be nonempty. We present a polynomial time algorithm that with high probability (over the random choice of random graph G, and without being given the planted independent set I) finds the maximum independent set in G when α > c0 / √ d , where c0 is some sufficiently large constant independent of d.

Routing Complexity of Faulty Networks: One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the failure probability can be, before the capability to efficiently find a path in the network is lost. Our main results show tight upper and lower bounds for the failure probability which permits routing, both for the hypercube and for the d-dimensional mesh. We use tools from percolation theory to show that in the d-dimensional mesh, once a giant component appears - efficient routing is possible. A different behavior is observed when the hypercube is considered. In the hypercube there is a range of failure probabilities in which short paths exist with high probability, yet finding them must involve querying essentially the entire network. Thus the routing complexity of the hypercube shows an asymptotic phase transition. The critical probability with respect to routing complexity lies in a different location then that of the critical probability with respect to connectivity. Finally we show that an oracle access to links (as opposed to local routing) may reduce significantly the complexity of the routing problem. We demonstrate this fact by providing tight upper and lower bounds for the complexity of routing in the random graph Gn,p.

Easily refutable subformulas of large random 3CNF formulas: A simple nonconstructive argument shows that most 3CNF formulas with cn clauses (where c is a large enough constant) are not satisfiable. It is an open question whether there is an efficient refutation algorithm that for most formulas with cn clauses proves that they are not satisfiable. We present a polynomial time algorithm that for most 3CNF formulas with cn3/2 clauses(where c is a large enough constant) finds a subformula with O(c2 n) clauses and then proves that this subformula is not satisfiable (and hence that the original formula is not satisfiable). Previously, it was only known how to efficiently certify the unsatisfiability of random 3CNF formulas with at least poly(log(n)) n3/2 clauses.We present some preliminary experimental results.

Spectral Techniques Applied to Sparse Random Graphs: We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let λ1 λ2 … λn be the eigenvalues of an n-vertex graph, and let λ = max[λ2, |λn|]. Let c be a large enough constant. For graphs of average degree d = c log n it is well known that λ1 d, and we show that λ = O(√d). For d=c it is no longer true that λ = O(√d), but we show that by removing a small number of vertices of highest degree in G, one gets a graph G' for which λ = O(√d). Our proofs are based on the techniques of Kahn and Szemeredi from STOC 1989, who proved similar results for regular graphs. Our results are useful for extending the analysis of certain heuristics to sparser instances of NP-hard problems. We illustrate this by removing some unnecessary logarithmic factors in the density of k-SAT formulas that are refuted by the algorithm of Goerdt and Krivelevich from STACS 2001. Our result also implies a bound on the probable value of the Lovasz Theta function for the Gn,c/n random graph model.

Approximating Maximum Edge Coloring in Multigraphs: We study the complexity of the following problem that we call Max edge t-coloring: given a multigraph G and a parameter t, color as many edges as possible using t colors, such that no two adjacent edges are colored with the same color. (Equivalently, find the largest edge induced subgraph of G that has chromatic index at most t). We show that for every fixed t 2 there is some ε > 0 such that it is NP-hard to approximate Max edge t-coloring within a ratio better than 1 - ε. We design approximation algorithms for the problem with constant factor approximation ratios. An interesting feature of our algorithms is that they allow us to estimate the value of the optimum solution up to a multiplicative factor that tends to 1 as t grows. Our study was motivated by call admittance issues in satellite based telecommunication networks.