counting quantifiers

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

Fixed-point logic with counting ★★

Author(s): Blass

\begin{question} Can either of the following be expressed in fixed-point logic plus counting: \begin{enumerate} \item Given a graph, does it have a perfect matching, i.e., a set $M$ of edges such that every vertex is incident to exactly one edge from $M$? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant? \end{enumerate} \end{question}

Keywords: Capturing PTime; counting quantifiers; Fixed-point logic; FMT03-Bedlewo

Syndicate content