Bridging Weighted First Order Model Counting and Graph Polynomials
- URL: http://arxiv.org/abs/2407.11877v1
- Date: Tue, 16 Jul 2024 16:01:25 GMT
- Title: Bridging Weighted First Order Model Counting and Graph Polynomials
- Authors: Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, Yuyi Wang,
- Abstract summary: Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a domain.
We define Weak Connectedness Polynomial and Strong Connectedness Polynomials for first-order logic sentences.
- Score: 6.2686964302152735
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 also 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, being a spanning subgraph, 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, which allows us to show that these important graph polynomials can be computed in time polynomial in the number of vertices for any graph that can be encoded by a fixed $C^2$ sentence and a conjunction of an arbitrary number of ground unary literals.
Related papers
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ under isotropic Gaussian data.
We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ of arbitrary link function with a sample and runtime complexity of $n asymp T asymp C(q) cdot d
arXiv Detail & Related papers (2024-06-03T17:56:58Z) - 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) - Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators [0.3177496877224142]
The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems.
In this paper we attack this problem using the algebraic structure of QMC, in particular the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group.
arXiv Detail & Related papers (2023-07-28T16:45:16Z) - 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) - 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) - Horizon-Free Reinforcement Learning in Polynomial Time: the Power of
Stationary Policies [88.75843804630772]
We design an algorithm that achieves an $Oleft(mathrmpoly(S,A,log K)sqrtKright)$ regret in contrast to existing bounds.
Our result relies on a sequence of new structural lemmas establishing the approximation power, stability, and concentration property of stationary policies.
arXiv Detail & Related papers (2022-03-24T08:14:12Z) - 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) - 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.