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

TR03-010 | 13th February 2003
Sven Baumer, Rainer Schuler

Improving a probabilistic 3-SAT Algorithm by Dynamic Search and Independent Clause Pairs

The satisfiability problem of Boolean Formulae in 3-CNF (3-SAT)
is a well known NP-complete problem and the development of faster
(moderately exponential time) algorithms has received much interest
in recent years. We show that the 3-SAT problem can be solved by a
probabilistic algorithm in expected time O(1,3290^n).
more >>>


TR03-009 | 3rd February 2003
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

Private Computation --- $k$-connected versus $1$-connected Networks

Revisions: 1

We study the role of connectivity of communication networks in private
computations under information theoretic settings. It will be shown that
some functions can be computed by private protocols even if the
underlying network is 1-connected but not 2-connected. Then we give a
complete characterisation of non-degenerate functions that can ... more >>>


TR03-008 | 11th February 2003
Piotr Berman, Marek Karpinski

Improved Approximation Lower Bounds on Small Occurrence Optimization

We improve a number of approximation lower bounds for
bounded occurrence optimization problems like MAX-2SAT,
E2-LIN-2, Maximum Independent Set and Maximum-3D-Matching.

more >>>


previous PreviousNext next


ISSN 1433-8092 | Imprint