All reports by Author André Lanka:

__
TR04-048
| 21st April 2004
__

André Lanka, Andreas Goerdt#### An approximation hardness result for bipartite Clique

__
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

André Lanka, Andreas Goerdt

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 >>>

Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich

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 >>>