Improved inaproximability results are given, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems, like MAX-2SAT and E2-LIN-2, and problems in bounded degree graphs, like MIS, Node Cover and MAX CUT. We prove also for the first time inapproximability of the problem of Sorting by ... more >>>

We study small degree graph problems such as Maximum Independent Set and Minimum Node Cover and improve approximation lower bounds for them and for a number of related problems, like Max-B-Set Packing, Min-B-Set Cover, Max-Matching in B-uniform 2-regular hypergraphs. For example, we prove NP-hardness factor of 95/94 for Max-3-Dimensional Matching, ... more >>>

A $k$-uniform hypergraph $G$ of size $n$ is said to be $\varepsilon$-far from having an independent set of size $\rho n$ if one must remove at least $\varepsilon n^k$ edges of $G$ in order for the remaining hypergraph to have an independent set of size $\rho n$. In this work, ... more >>>

We give a new method for analysing the mixing time of a Markov chain using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree $\Delta$ of ... more >>>