Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Amin Coja-Oghlan:

TR06-116 | 19th July 2006
Amin Coja-Oghlan

Graph partitioning via adaptive spectral techniques

We study the use of spectral techniques for graph partitioning. Let G=(V,E) be a graph whose vertex set has a ``latent'' partition V_1,...,V_k. Moreover, consider a ``density matrix'' E=(E_vw)_{v,w in V} such that for v in V_i and w in V_j the entry E_{vw} is the fraction of all possible ... more >>>

TR03-073 | 11th June 2003
Amin Coja-Oghlan

The Lovasz number of random graph

We study the Lovasz number theta along with two further SDP relaxations $\thetI$, $\thetII$
of the independence number and the corresponding relaxations of the
chromatic number on random graphs G(n,p). We prove that \theta is
concentrated about its mean, and that the relaxations of the chromatic
number in the case ... 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