Post-publication notes and errata
Notes added to publications after they appeared: errors in stated results or proofs, clarifications of misleading statements, later developments that affect a paper, and typos. Each note is also shown with its entry in the publication list, and added to the PDF hosted on this site, as a banner on the first page and a page at the end.
-
, , and , Tractable Lineages on Treelike Instances: Limits and Extensions. April 2023. arXiv abs/1604.02761. (pdf | arXiv | bib)
Update
- Update : The introduction and Section 5.2 present the hypothesis of Theorem 5.5 as the non-uniform exponential-time hypothesis. The hypothesis actually used in the statement, and all the proof needs, is weaker: that the polynomial hierarchy is not contained in DTIME(2o(n))/SubEXP. The distinction now matters: a preprint released by OpenAI on October 25, 2026 claims a deterministic 2o(n)-time algorithm for 3-SAT, which would refute ETH and its non-uniform version but leaves this weaker hypothesis open. The other intractability results of the paper (Theorems 4.2, 5.2, and 5.7) are unconditional. The same applies to the conference version.
-
, , , and , Possible and Certain Answers for Queries over Order-Incomplete Data. In Proc. TIME, pp. 4:1–4:19, Mons, Belgium, October 2017. (pdf | extended version | doi | bib)
Erratum
- Erratum : Theorems 19, 22, and 30 (tractability of possibility for PosRA queries on unordered or bounded-ia-width po-databases, and of possibility and certainty for accumulation queries on bounded ia-width) are not established, and Theorems 19 and 22 are false unless P = NP: the proof of Proposition 66 of the first arXiv version fails for the product operators, and Theorem 92 of version 2 of the extended version (January 2018, hosted here) exhibits a PosRA query for which possibility is NP-complete on unordered po-relations. That version removes the affected results and discusses the error in its Appendix G; the journal version contains neither. See also Antoine Amarilli's errata.
-
Erratum Update
- Erratum : The proof of Theorem 5.5, given in Antoine Amarilli's PhD thesis (Theorem 6.2.5) rather than in the paper, is incorrect: the advice string it defines depends on the instance and not only on its size. A corrected proof is given in the appendix of version 2 of the extended version on arXiv (April 2023), which is the one hosted here. See also Antoine Amarilli's errata.
- Update : The introduction and Section 5.2 present the hypothesis of Theorem 5.5 as the non-uniform exponential-time hypothesis. The hypothesis actually used in the statement, and all the proof needs, is weaker: that the polynomial hierarchy is not contained in DTIME(2o(n))/SubEXP. The distinction now matters: a preprint released by OpenAI on October 25, 2026 claims a deterministic 2o(n)-time algorithm for 3-SAT, which would refute ETH and its non-uniform version but leaves this weaker hypothesis open. The other intractability results of the paper (Theorems 4.2, 5.2, and 5.7) are unconditional. The same applies to the extended version.
-
Erratum
- Erratum : As explained in the related-work section of our 2020 paper on monadic Datalog, two results are incorrect. The proof of the co2NEXPTIME lower bound of Theorem 5.6, for containment of positive queries under access limitations (and hence of the 2NEXPTIME-hardness of long-term relevance for positive queries), is flawed, and the bound is at odds, under standard complexity-theoretic assumptions, with the 2EXPTIME upper bound later proven by Benedikt, Bourhis, and Ley (ACM TODS 2015). The proof of the coNEXPTIME upper bound of Theorem 5.2, for conjunctive query containment under access limitations, only works for schemas with a single access method per relation; the general case is open. The same applies to the conference version.
-
Erratum
- Erratum : As explained in the related-work section of our 2020 paper on monadic Datalog, two results are incorrect. The proof of the co2NEXPTIME lower bound of Theorem 5.6, for containment of positive queries under access limitations (and hence of the 2NEXPTIME-hardness of long-term relevance for positive queries), is flawed, and the bound is at odds, under standard complexity-theoretic assumptions, with the 2EXPTIME upper bound later proven by Benedikt, Bourhis, and Ley (ACM TODS 2015). The proof of the coNEXPTIME upper bound of Theorem 5.2, for conjunctive query containment under access limitations, only works for schemas with a single access method per relation; the general case is open. The same applies to the extended version.
-
and , Schema Mapping Discovery from Data Instances. Journal of the ACM, 57(2), pp. 6:1–6:37, January 2010. (pdf | doi | bib)
Erratum
- Erratum : The proof of Proposition 5.8 is flawed (see footnote 1 of ten Cate, Kolaitis, Qian, and Tan, AMW 2015), and the DP-hardness of Optimality claimed in Propositions 5.8 and 5.9(5) and in Tables II and IV is not established. What holds, as stated in the conference version, is that Optimality is NP-hard and coNP-hard, and that Existence-Cost is NP-hard.