Previous Conferences & Workshops

We consider the following two questions: 1) Is the MAX-CUT problem hard on random geometric graphs of the type considered by Feige and Schechtman (2002)? 2) Is the value of a mathematical relaxation such as semi- definite programming (SDP) for a...

The small-set expansion conjecture introduced by Raghavendra and Steuerer is a natural hardness assumption concerning the problem of approximating edge expansion of small sets (of size $\delta n$) in graphs. It was shown to be intimately connected...