![](/files/happy5.png)
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
.
![$ \varepsilon > 0 $](/files/tex/5100aa83a735c347ff2a904d4fc00eb99293313b.png)
![$ \delta > 0 $](/files/tex/7f1f08ff9938cb9a6981c1f1e563b40b7c34396a.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ G \equiv_{\delta n}^{\mathrm{C}} H $](/files/tex/bde71bc721de861f937e9c0d2e1c9c1d1ee7a71b.png)
![$ \mathrm{vc}(G) \ge (2 - \varepsilon) \cdot \mathrm{vc}(H) $](/files/tex/1e471324d6f347bdb5fb4e462749473752a10170.png)
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?
Keywords: bounded tree width; Computational Complexity; FMT12-LesHouches; QBF
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.
Keywords: FMT12-LesHouches; MSO, alternation hierarchy; picture languages
Order-invariant queries ★★
Author(s): Segoufin
Question
- \item Does
![$ {<}\text{-invariant\:FO} = \text{FO} $](/files/tex/e707bf924cc12f72d2ce6921ded07bb2e489e3d2.png)
![$ {<}\text{-invariant\:FO} $](/files/tex/275592d2a0f85bf01139441abb9bce5b40ac7d32.png)
![$ \text{MSO} $](/files/tex/e4f938d499ee26825afedaf106892a7ca85e30ae.png)
![$ {<}\text{-invariant\:FO} $](/files/tex/275592d2a0f85bf01139441abb9bce5b40ac7d32.png)
![$ {<}\text{-invariant\:FO} $](/files/tex/275592d2a0f85bf01139441abb9bce5b40ac7d32.png)
![$ {<}\text{-invariant\:FO} $](/files/tex/275592d2a0f85bf01139441abb9bce5b40ac7d32.png)
Keywords: Effective syntax; FMT12-LesHouches; Locality; MSO; Order invariance
![Syndicate content Syndicate content](/misc/feed.png)