No article text was recorded for this version.
model counting complexity
Version 2 of 2304 papers372 conceptsfrozen 2026-10-04
Papers in this version
- Blog: On the Hardness of Approximate Reasoning Dan Roth
- Blog: Preprocessing for Propositional Model Counting
- Blog: Tally NP Sets and Easy Census Functions
- Blog: Generating Models of a Matched Formula With a Polynomial Delay (Extended Abstract)
- Blog: Knowledge-Base Degrees of Inconsistency: Complexity and Counting
- Blog: Approximate Resolution of Hard Numbering Problems
- Blog: The Consequences of Eliminating NP Solutions
- Blog: On the Hardness of Approximate Reasoning
- Blog: The consequences of eliminating NP solutions
- Blog: Approximate Counting via Correlation Decay on Planar Graphs
- Blog: Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle?
- Blog: On the Hardness of Probabilistic Inference Relaxations
- Blog: Counting Complexity of Propositional Abduction
- Blog: Counting Problems over Incomplete Databases
- Blog: Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases
- Blog: Symmetric Weighted First-Order Model Counting
- Blog: Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting
- Blog: Counting without sampling: new algorithms for enumeration problems using statistical physics
- Blog: Nobuhiro Yugam
- Blog: Relational Algorithms for k-means Clustering
- Blog: Computational complexity of numberless Shakashaka
- Blog: On SAT Models Enumeration in Itemset Mining
- Blog: Distribution-Aware Sampling and Weighted Model Counting for SAT
- Blog: Projected Model Counting
- Blog: DNF Sparsification and a Faster Deterministic Counting Algorithm
- Blog: Why Concept Lattices Are Large - Extremal Theory for the Number of Minimal Generators and Formal Concepts
- Blog: Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
- Blog: DMC: A Distributed Model Counter
- Blog: The Complexity of Counting Problems over Incomplete Databases
- Blog: Plausibility Reasoning via Projected Answer Set Counting - A Hybrid Approach
- Blog: On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results
- Blog: Computational Complexity of Statistical Machine Translation
- Blog: Correlation decay and deterministic FPTAS for counting list-colorings of a graph
- Blog: Towards Real-Time Approximate Counting
- Blog: A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
- Blog: Approximate SMT Counting Beyond Discrete Domains
- Blog: Computing Preferences Based on Agents' Beliefs
- Blog: Algorithmic Improvements in Approximate Counting for Probabilistic Inference: From Linear to Logarithmic SAT Calls
- Blog: International Competition on Graph Counting Algorithms 2023
- Blog: Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration with Provable Guarantees
- Blog: Computing Intersections of Horn Theories for Reasoning with Models
- Blog: Zeros of Holant problems: locations and algorithms
- Blog: On the Hardness of Approximate Reasoning
- Blog: Epistemic Logic Programs: Non-Ground and Counting Complexity
- Blog: A complexity theory for hard enumeration problems
- Blog: On Compiling CNF into Decision-DNNF
- Blog: Tractability Beyond β-Acyclicity for Conjunctive Queries with Negation
- Blog: Counting Solutions of Constraint Satisfiability Problems:Exact Phase Transitions and Approximate Algorithm
- Blog: Counting the Number of Solutions to Constraints
- Blog: Counting hypergraph matchings up to uniqueness threshold
- Blog: Distribution-Aware Sampling and Weighted Model Counting for SAT
- Blog: Counting Models using Extension Rules
- Blog: Engineering an Efficient Approximate DNF-Counter
- Blog: Compilation and Fast Model Counting beyond CNF
- Blog: A Tool for Computing and Estimating the Volume of the Solution Space of SMT(LA)
- Blog: Engineering an Efficient Approximate DNF-Counter
- Blog: Canonical Paths for MCMC: from Art to Science
- Blog: $\text{#NFA}$ admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
- Blog: On Computing the Number of Latin Rectangles
- Blog: #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
Showing 60 of 304 papers.
History & citation
Current · Permanent link
Cite this direction
Latest version (a living page):
@misc{lacuna_model_counting_complexity_f9e50e4e,
title = {model counting complexity},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/model-counting-complexity/rdr_f9e50e4e0a7342e4aac8d1cb636ebb58},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}This exact version (version 2, frozen text):
@misc{lacuna_model_counting_complexity_f9e50e4e_v2,
title = {model counting complexity},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/model-counting-complexity/rdr_f9e50e4e0a7342e4aac8d1cb636ebb58/v/2},
note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}