Bridging Weighted First Order Model Counting and Graph Polynomials

• URL: http://arxiv.org/abs/2407.11877v2
• Date: Tue, 26 Nov 2024 03:00:54 GMT
• Title: Bridging Weighted First Order Model Counting and Graph Polynomials
• Authors: Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, Yuyi Wang,
• Abstract summary: We use Weak Connectedness Polynomial and Strong Connectedness Polynomials for first-order logic sentences. We can use them to solve WFOMC with all of the existing axioms known to be tractable.
• Score: 6.2686964302152735
• License:
• Abstract: The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. It can be solved in time polynomial in the domain size for sentences from the two-variable fragment with counting quantifiers, known as $C^2$. This polynomial-time complexity is known to be retained when extending $C^2$ by one of the following axioms: linear order axiom, tree axiom, forest axiom, directed acyclic graph axiom or connectedness axiom. An interesting question remains as to which other axioms can be added to the first-order sentences in this way. We provide a new perspective on this problem by associating WFOMC with graph polynomials. Using WFOMC, we define Weak Connectedness Polynomial and Strong Connectedness Polynomials for first-order logic sentences. It turns out that these polynomials have the following interesting properties. First, they can be computed in polynomial time in the domain size for sentences from $C^2$. Second, we can use them to solve WFOMC with all of the existing axioms known to be tractable as well as with new ones such as bipartiteness, strong connectedness, having $k$ connected components, etc. Third, the well-known Tutte polynomial can be recovered as a special case of the Weak Connectedness Polynomial, and the Strict and Non-Strict Directed Chromatic Polynomials can be recovered from the Strong Connectedness Polynomials.

Related papers

• On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors [1.249418440326334]
  We characterize maximal families over the binary field $mathbbF$. Our findings prompt several more open questions, which we plan to address in an extended version of this work.
  arXiv  Detail & Related papers  (2024-05-14T16:30:28Z)
• Lifted Inference beyond First-Order Logic [8.577974472273256]
  We show that any $mathrmC2$ sentence remains domain liftable when one of its relational properties is a directed acyclic graph, a connected graph, a tree or a forest. Our results rely on a novel and general methodology of "counting by splitting"
  arXiv  Detail & Related papers  (2023-08-22T18:58:21Z)
• Weighted First Order Model Counting with Directed Acyclic Graph Axioms [7.766921168069532]
  Probabilistic inference and learning in many SRL can be reduced to Weighted First Model Counting (WFOMC) WFOMC is known to be intractable ($mathrm#P$ complete) We show that the fragment $mathrmC2$ with a Directed Acyclic Graph (DAG)exclusion, i.e., a axiomatized to represent axiom DAG, is domain liftable.
  arXiv  Detail & Related papers  (2023-02-20T08:35:13Z)
• A Direct Reduction from the Polynomial to the Adversary Method [92.54311953850168]
  We give a simple and direct reduction from the method (in the form of a dual) to the adversary method. This shows that any lower bound in the form of a dual is an adversary lower bound of a specific form.
  arXiv  Detail & Related papers  (2023-01-24T21:37:20Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• Lifted Inference with Linear Order Axiom [0.0]
  We consider the task of weighted first-order model counting (WFOMC) We show that WFOMC of any logical sentence with at most two logical variables can be done in time in $n$. We present a new dynamic programming-based algorithm which can compute WFOMC with linear order in time in $n$.
  arXiv  Detail & Related papers  (2022-11-02T14:38:01Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• Weighted Model Counting in the two variable fragment with Cardinality Constraints: A Closed Form Formula [7.766921168069532]
  Weighted First-Order Model Counting (WFOMC) computes the weighted sum of the models of a first-order theory on a given finite domain. We introduce the concept of lifted interpretations as a tool for formulating inferences for WFOMC. We then expand this closed-form to incorporate existential quantifiers and cardinality constraints without losing domain-liftability.
  arXiv  Detail & Related papers  (2020-09-25T13:50:18Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURF is an algorithm for approximating distributions by piecewises. It outperforms state-of-the-art algorithms in experiments.
  arXiv  Detail & Related papers  (2020-02-22T01:03:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.