
counting quantifiers
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
Fixed-point logic with counting ★★
Author(s): Blass
Question Can either of the following be expressed in fixed-point logic plus counting:
- \item Given a graph, does it have a perfect matching, i.e., a set


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