# FMT12-LesHouches

## Vertex Cover Integrality Gap ★★

Author(s): Atserias

Conjecture   For every there is such that, for every large , there are -vertex graphs and such that and .

Keywords: counting quantifiers; FMT12-LesHouches

## Complexity of QBF(Bounded Treewidth) ★★

Author(s): Moshe Y. Vardi

Question   What is the computational complexity of QBF(Bounded Treewidth)? Is it PSPACE-complete? In PTIME?

## MSO alternation hierarchy over pictures ★★

Author(s): Grandjean

Question   Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linearly) related.

## Order-invariant queries ★★

Author(s): Segoufin

Question
\item Does hold over graphs of bounded tree-width? \item Is included in over graphs? \item Does have a 0-1 law? \item Are properties of Hanf-local? \item Is there a logic (with an effective syntax) that captures ?