Vertex Cover Integrality Gap ★★

Author(s): Atserias

\begin{conjecture} For every $\varepsilon > 0$ there is $\delta > 0$ such that, for every large $n$, there are $n$-vertex graphs $G$ and $H$ such that $G \equiv_{\delta n}^{\mathrm{C}} H$ and $\mathrm{vc}(G) \ge (2 - \varepsilon) \cdot \mathrm{vc}(H)$. \end{conjecture}

Keywords: counting quantifiers; FMT12-LesHouches

Complexity of QBF(Bounded Treewidth) ★★

Author(s): Moshe Y. Vardi

\begin{question} What is the computational complexity of QBF(Bounded Treewidth)? Is it PSPACE-complete? In PTIME? \end{question}

Keywords: bounded tree width; Computational Complexity; FMT12-LesHouches; QBF

MSO alternation hierarchy over pictures ★★

Author(s): Grandjean

\begin{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. \end{question}

Keywords: FMT12-LesHouches; MSO, alternation hierarchy; picture languages

Order-invariant queries ★★

Author(s): Segoufin

\begin{question} \begin{enumerate} \item Does ${<}\text{-invariant\:FO} = \text{FO}$ hold over graphs of bounded tree-width? \item Is ${<}\text{-invariant\:FO}$ included in $\text{MSO}$ over graphs? \item Does ${<}\text{-invariant\:FO}$ have a 0-1 law? \item Are properties of ${<}\text{-invariant\:FO}$ Hanf-local? \item Is there a logic (with an effective syntax) that captures ${<}\text{-invariant\:FO}$? \end{enumerate} \end{question}

Keywords: Effective syntax; FMT12-LesHouches; Locality; MSO; Order invariance

Syndicate content