9 problems

Let $cmu$ be a union of connected conjunctive queries over a signature $ctau$, let $cDelta_cmu$ be the associated valued structure, and let $cmathfrak A$ be a finitely bounded homo…

Under bag semantics, the resilience problem for a fixed union of conjunctive queries $cmu$ asks whether, given a database and a number $u$, at most $u$ tuples can be removed so tha…

Resilience tractability conjecture. If the structure $(\{0,1\};\operatorname{OIT})$ has no pp-construction in $\Gamma$, then $\Gamma$ has a fractional polymorphism of arity…

Resilience tractability conjecture. The resulting algorithm solves all resilience problems that are in $\operatorname{P}$.

Hardness-condition conjecture for homogeneous reducts. Under the stated automorphism-group hypothesis, the hardness condition is not only sufficient but also necessary for VCSPs st…

Hardness-condition conjecture. For VCSPs that stem from resilience problems, the hardness condition is not only sufficient but also necessary, unless…

Resilience complexity conjecture. The hardness and tractability conditions should match for resilience problems for unions of conjunctive queries.

Let $\mathbf{fus}$ denote the class of rulesets considered in the paper, and let finite controllability mean that query entailment over such rulesets can be determined using finite…

Fix a standard encoding of structures by binary strings. A Turing machine $M$ is generic if the set of structures $S$ such that $M$ accepts the standard string encoding of $S$ is c…