My PhD thesis. Rigorous Analysis of Heuristics for NP-hard Problems.
June 2006.
[(pdf) | (ps)]
Witnesses for non-satisfiability of dense random 3CNF formulas.
U. Feige, Jeong Han Kim , E. Ofek
To appear in FOCS 2006.
[(pdf) | (ps) | abstract]
Random 3CNF formulas elude the Lovasz theta function.
U. Feige, E. Ofek
[(pdf) | (ps) | abstract]
On the expansion of the giant component in percolated (n,d,λ) graphs.
E. Ofek
To appear in Combinatorics, Probability and Computing.
[(pdf) | (ps) | abstract]
Finding a maximum independent set in a sparse random graph. U. Feige, E. Ofek RANDOM 2005.
[(ppt) | (pdf) | full version(pdf) | abstract]
Spectral Techniques Applied to Sparse Random Graphs.
U. Feige, E. Ofek
Random Structures and Algorithms, 27(2), 251--275, September 2005.
[(pdf) | (ps) | abstract]
Approximating Maximum Edge Coloring in Multigraphs.
U. Feige, E. Ofek, U. Wieder
APPROX 2002.
[(ppt) | (pdf) | (ps) | abstract]