All reports by Author Eran Ofek:

__
TR06-043
| 22nd March 2006
__

Eran Ofek, Uriel Feige#### Random 3CNF formulas elude the Lovasz theta function

__
TR05-112
| 12th September 2005
__

Eran Ofek#### On the expansion of the giant component in percolated $(n,d,\lambda)$ graphs

Revisions: 1

__
TR05-050
| 18th April 2005
__

Uriel Feige, Eran Ofek#### Finding a Maximum Independent Set in a Sparse Random Graph

Revisions: 1

Eran Ofek, Uriel Feige

Let $\phi$ be a 3CNF formula with n variables and m clauses. A

simple nonconstructive argument shows that when m is

sufficiently large compared to n, most 3CNF formulas are not

satisfiable. It is an open question whether there is an efficient

refutation algorithm that for most such formulas proves ...
more >>>

Eran Ofek

Let $d \geq d_0$ be a sufficiently large constant. A $(n,d,c

\sqrt{d})$ graph $G$ is a $d$ regular graph over $n$ vertices whose

second largest eigenvalue (in absolute value) is at most $c

\sqrt{d}$. For any $0 < p < 1, ~G_p$ is the graph induced by

retaining each edge ...
more >>>

Uriel Feige, Eran Ofek

We consider the problem of finding a maximum independent set in a

random graph. The random graph $G$ is modelled as follows. Every

edge is included independently with probability $\frac{d}{n}$, where

$d$ is some sufficiently large constant. Thereafter, for some

constant $\alpha$, a subset $I$ of $\alpha n$ vertices is ...
more >>>