Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR00-020 | 27th March 2000
Oded Goldreich, Dana Ron

On Testing Expansion in Bounded-Degree Graphs


We consider testing graph expansion in the bounded-degree graph model.
Specifically, we refer to algorithms for testing whether the graph
has a second eigenvalue bounded above by a given threshold
or is far from any graph with such (or related) property.

We present a natural algorithm aimed ... more >>>


TR00-019 | 20th March 2000
Edward Hirsch

Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search

During the past three years there was an explosion of algorithms
solving MAX-SAT and MAX-2-SAT in worst-case time of the order
c^K, where c<2 is a constant, and K is the number of clauses
in the input formula. Such bounds w.r.t. the number of variables
instead of the number of ... more >>>


TR00-018 | 16th February 2000
Oliver Kullmann

An application of matroid theory to the SAT problem

A basic property of minimally unsatisfiable clause-sets F is that
c(F) >= n(F) + 1 holds, where c(F) is the number of clauses, and
n(F) the number of variables. Let MUSAT(k) be the class of minimally
unsatisfiable clause-sets F with c(F) <= n(F) + k.

Poly-time decision algorithms are known ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint