Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author André Lanka:

TR04-048 | 21st April 2004
André Lanka, Andreas Goerdt

An approximation hardness result for bipartite Clique

Assuming 3-SAT formulas are hard to refute
on average, Feige showed some approximation hardness
results for several problems like min bisection, dense
$k$-subgraph, max bipartite clique and the 2-catalog segmentation
problem. We show a similar result for
max bipartite clique, but under the assumption, 4-SAT formulas
are hard to refute ... more >>>

TR03-030 | 27th February 2003
Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich

Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques

Abstract. It is known that random k-SAT formulas with at least
(2^k*ln2)*n random clauses are unsatisfiable with high probability. This
result is simply obtained by bounding the expected number of satisfy-
ing assignments of a random k-SAT instance by an expression tending
to 0 when n, the number of variables ... more >>>

ISSN 1433-8092 | Imprint