Weighted model counting beyond two-variable logic
Not on the map. Why?
Abstract (arXiv)
It was recently shown by van den Broeck at al. that the symmetric weighted first-order model counting problem (WFOMC) for sentences of two-variable logic FO2 is in polynomial time, while it is Sharp-P1 complete for some FO3-sentences. We extend the result for FO2 in two independent directions: to sentences of the form "phi and forallexists^=1 psi" with phi and psi in FO2, and to sentences formulated in the uniform one-dimensional fragment of FO, a recently introduced extension of two-variable logic with the capacity to deal with relation symbols of all arities. Note that the former generalizes the extension of FO2 with a functional relation symbol. We also identify a complete classification of first-order prefix classes according to whether WFOMC is in polynomial time or Sharp-P1 complete.
Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). First posted on arXiv 26 Apr 2018.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1; 2022: 2; 2023: 5; 2024: 1; 2025: 3; 2026: 1.
13 papers.
Sort:
- 2022Lifted Inference with Linear Order Axiomcited by 13
- 2021Weighted Model Counting in FO2 with Cardinality Constraints and Counting Quantifiers: A Closed Form Formulacited by 8
- 2023Lifted Algorithms for Symmetric Weighted First-Order Model Samplingcited by 6
- 2022On Projectivity in Markov Logic Networkscited by 5
- 2023Lifted Inference beyond First-Order Logiccited by 5
- 2024Bridging Weighted First Order Model Counting and Graph Polynomialscited by 5
- 2023On Exact Sampling in the Two-Variable Fragment of First-Order Logiccited by 3
- 2025Faster Lifting for Ordered Domains with Predecessor Relationscited by 2
- 2023Weighted First Order Model Counting with Directed Acyclic Graph Axiomscited by 1
- 2023Synthesising Recursive Functions for First-Order Model Counting: Challenges, Progress, and Conjecturescited by 1
- 2025Polynomial-Time Relational Probabilistic Inference in Open Universescited by 1
- 2025Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relationscited by 1
1 more
- 2026Solving Combinatorial Counting Problems with Weighted First-Order Model Counting24 May 2026
- 2025Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations15 Aug 2025
- 2025Faster Lifting for Ordered Domains with Predecessor Relations25 Jul 2025
- 2025Polynomial-Time Relational Probabilistic Inference in Open Universes7 May 2025
- 2024Bridging Weighted First Order Model Counting and Graph Polynomials16 Jul 2024
- 2023Lifted Inference beyond First-Order Logic22 Aug 2023
- 2023Lifted Algorithms for Symmetric Weighted First-Order Model Sampling17 Aug 2023
- 2023Synthesising Recursive Functions for First-Order Model Counting: Challenges, Progress, and Conjectures7 Jun 2023
- 2023Weighted First Order Model Counting with Directed Acyclic Graph Axioms20 Feb 2023
- 2023On Exact Sampling in the Two-Variable Fragment of First-Order Logic6 Feb 2023
- 2022Lifted Inference with Linear Order Axiom2 Nov 2022
- 2022On Projectivity in Markov Logic Networks8 Apr 2022
- 2022Lifted Inference with Linear Order Axiomcited by 13
- 2021Weighted Model Counting in FO2 with Cardinality Constraints and Counting Quantifiers: A Closed Form Formulacited by 8
- 2023Lifted Algorithms for Symmetric Weighted First-Order Model Samplingcited by 6
- 2022On Projectivity in Markov Logic Networkscited by 5
- 2023Lifted Inference beyond First-Order Logiccited by 5
- 2024Bridging Weighted First Order Model Counting and Graph Polynomialscited by 5
- 2023On Exact Sampling in the Two-Variable Fragment of First-Order Logiccited by 3
- 2025Faster Lifting for Ordered Domains with Predecessor Relationscited by 2
- 2023Weighted First Order Model Counting with Directed Acyclic Graph Axiomscited by 1
- 2023Synthesising Recursive Functions for First-Order Model Counting: Challenges, Progress, and Conjecturescited by 1
- 2025Polynomial-Time Relational Probabilistic Inference in Open Universescited by 1
- 2025Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relationscited by 1
12 most cited of 13 All 13 (JSON)
- 2026Solving Combinatorial Counting Problems with Weighted First-Order Model Counting24 May 2026
- 2025Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations15 Aug 2025
- 2025Faster Lifting for Ordered Domains with Predecessor Relations25 Jul 2025
- 2025Polynomial-Time Relational Probabilistic Inference in Open Universes7 May 2025
- 2024Bridging Weighted First Order Model Counting and Graph Polynomials16 Jul 2024
- 2023Lifted Inference beyond First-Order Logic22 Aug 2023
- 2023Lifted Algorithms for Symmetric Weighted First-Order Model Sampling17 Aug 2023
- 2023Synthesising Recursive Functions for First-Order Model Counting: Challenges, Progress, and Conjectures7 Jun 2023
- 2023Weighted First Order Model Counting with Directed Acyclic Graph Axioms20 Feb 2023
- 2023On Exact Sampling in the Two-Variable Fragment of First-Order Logic6 Feb 2023
- 2022Lifted Inference with Linear Order Axiom2 Nov 2022
- 2022On Projectivity in Markov Logic Networks8 Apr 2022
12 newest of 13 All 13 (JSON)