All reports by Author Amin Coja-Oghlan:

__
TR06-116
| 19th July 2006
__

Amin Coja-Oghlan#### Graph partitioning via adaptive spectral techniques

__
TR03-073
| 11th June 2003
__

Amin Coja-Oghlan#### The Lovasz number of random graph

__
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

Amin Coja-Oghlan

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

Amin Coja-Oghlan

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

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