We give the first polynomial time approximability characterization
of dense weighted instances of MAX-CUT, and some other dense
weighted NP-hard problems in terms of their empirical weight
distributions. This gives also the first almost sharp
characterization of inapproximability of unweighted 0,1
MAX-BISECTION instances ... more >>>

We present some of the recent results on computational complexity
of approximating bounded degree combinatorial optimization problems. In
particular, we present the best up to now known explicit nonapproximability
bounds on the very small degree optimization problems which are of
particular importance on the intermediate stages ... more >>>

This paper studies the existence of efficient (small size)
amplifiers for proving explicit inaproximability results for bounded degree
and bounded occurrence combinatorial optimization problems, and gives
an explicit construction for such amplifiers. We use this construction
also later to improve the currently best known approximation lower bounds
more >>>