Pith. sign in

REVIEW 2 major objections 6 minor 61 references

On Symbolic Approaches for Computing the Matrix Permanent

T0 review · 2 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Computing a matrix permanent is usually practical only for sparse matrices; this paper shows that a symbolic version of Ryser's formula, built on Algebraic Decision Diagrams, computes exact permanents of dense 70x70 and similar-row 80x80…

desk verdict Clean symbolic-Ryser algorithm with real promise on structured matrices, but the 'dense' claim is supported only by near-all-ones benchmarks and needs tightening. read the letter →

arxiv 1908.03252 v1 pith:EZET4JUZ submitted 2019-08-08 cs.DS cs.SC

Supratik Chakraborty , Aditya A. Shrotri , Moshe Y. Vardi This is my paper · ORCID
classification cs.DScs.SC
keywords matrixpermanentalgebraicdecisiondiagramsRyser'sformulasymboliccomputationexactcountingperfectmatchings0-1matricesearlyabstraction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether exact computation of the matrix permanent, a #P-complete problem usually tackled only for sparse inputs, can be pushed to dense and row-similar matrices. It answers yes: encode the matrix as an Algebraic Decision Diagram and run Ryser's inclusion-exclusion formula symbolically, letting the diagram share repeated partial computations. The experiments show exact permanents of $70\times 70$ dense 0-1 matrices and $80\times 80$ matrices with almost identical rows computed within 1800 seconds; in the same setting the explicit Gray-code implementation of Ryser's algorithm times out for $n\ge 34$, while the compared SAT-based counters time out on all dense instances of size 30 and all similar-row instances of size 40. The message is that compact symbolic representation, not sparsity alone, is a workable route to practical permanent computation.

What carries the argument

The central object is the Algebraic Decision Diagram (ADD), a directed acyclic graph representing a real-valued function of Boolean variables by sharing identical substructures. Here the Boolean variables say whether a column belongs to the subset $S$ in Ryser's formula; the ADD's leaves carry integer values such as row sums, products, and the parity sign $(-1)^{|S|}$. The diagram does the work: when rows are identical or similar, the row-sum ADDs are isomorphic and merge, and memoization through shared nodes avoids recomputing the same partial sums. The supporting mechanism is early abstraction, the identity $\exists x\,(f\cdot g)=(\exists x\,f)\cdot g$ when $x$ does not occur in $g$, which lets the algorithm quantify out column variables as soon as they are irrelevant, keeping the diagram small. The experiments show a strong correlation between ADD node count and running time, confirming that diagram size is the operative resource.

What would settle it

Run the proposed algorithm on random 0-1 matrices of size $n=40$ or $n=50$ in which each entry is independently 1 with probability 0.5, recording the maximum ADD node count and wall-clock time, and compare with the flipped-from-all-ones instances of the same size. If the ADD size jumps to millions of nodes or the run exceeds the 1800-second timeout even at $n=40$, the dense-matrix conclusion does not extend to arbitrary dense inputs; if it completes quickly, the claim is strengthened.

Watch

Extended reading notes

Core claim

The central discovery is that a symbolic implementation of Ryser's formula, built on Algebraic Decision Diagrams and driven by early abstraction, opens a practical frontier beyond sparse matrices. For an $n\times n$ 0-1 matrix the paper represents, as an ADD, the function $(-1)^{|S|}\prod_{i=1}^{n}\sum_{j\in S}a_{i,j}$ on subsets $S$ of columns; the permanent is obtained by adding the values over all $S$. Row sums for similar rows become shared subgraphs, so the diagram stays small exactly when rows are near-identical; early abstraction then eliminates a column variable as soon as no remaining row-sum factor depends on it. On 2125 generated benchmarks, exact permanents are reported for dense matrices up to $n=70$ and similar-row matrices up to $n=80$ within 1800 seconds, whereas the explicit implementation of Ryser's formula times out for $n\ge 34$ and neither SAT-based counter can solve the smallest dense or similar-row instances tested. The authors present this as first evidence that the frontier of practically efficient permanent computation can be pushed well beyond sparse matrices.

Load-bearing premise

The load-bearing premise is that the matrices used for the dense case, generated by flipping a few entries of the all-ones matrix, stand in for dense matrices as a class; if arbitrary dense 0-1 matrices make the decision diagram grow explosively, the main claim about dense matrices would not be supported.

Editorial extensions

If this is right

  • Exact permanent computation becomes practical for dense 0-1 matrices up to at least $n=70$, roughly double the limit of the explicit implementation of Ryser's formula used in the comparison.
  • Matrices whose rows differ in only a few positions can be solved up to $n=80$, with performance degrading gracefully as row similarity decreases.
  • With early abstraction, the same symbolic algorithm remains competitive with SAT-based counters on sparse matrices and outperforms them as density grows.
  • ADD size is the predictive resource: instances with compact diagrams run quickly, so heuristics that maximize subgraph sharing should be the focus of further work.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the dense benchmarks are built by flipping at most $1.4n$ entries of the all-ones matrix, so every row remains close to every other; arbitrary dense matrices, such as independent random entries with density 0.5, may not admit compact ADDs and are not covered by the experiments.
  • Editorial inference: the same ADD-plus-early-abstraction recipe could be applied to other subset-sum factorizations, such as counting Hamiltonian cycles or monomer-dimer partition functions, whenever the summed quantity factorizes row-wise and rows repeat structure.
  • Editorial inference: the correlation between ADD size and running time suggests a testable design principle - row ordering and clustering that maximize shared subgraphs should transfer to other decision-diagram libraries and to weighted model counting.
  • Editorial inference: a complete characterization of matrices with succinct ADD representations would let the approach yield theoretical upper bounds for dense matrices analogous to the earlier sparse-matrix bounds, a direction the authors leave open.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper presents RysersADD, an exact algorithm for computing the permanent of a 0-1 matrix by translating Ryser's formula into operations on Algebraic Decision Diagrams (ADDs). Row sums are represented as ADDs, multiplied with a parity ADD, and the permanent is obtained by additively quantifying out all column variables. An early-abstraction step, taken from the ADDMC weighted model counter, allows variables to be eliminated as soon as they no longer occur in future factors. The authors report experiments on random sparse, dense, and 'similar-row' matrices (generated by flipping O(n) entries of an all-zero, all-one, or repeated-row starting matrix), plus SuiteSparse and fullerene instances. RysersADD and the parallel version RysersADD-P solve dense instances up to n=70 and similar-row instances up to n=80 within 1800 seconds, while explicit Ryser and the model counters D4 and DSharp time out earlier. The paper concludes that the frontier of practical permanent computation is pushed beyond sparse matrices to dense and similar-row matrices.

Significance. The algorithmic idea is clean and exact: it is a direct symbolic execution of Ryser's formula with no fitted parameters, and the early-abstraction theorem from ADDMC is used as a proven building block. The experimental study is broad in its coverage of baselines (explicit Ryser, D4, DSharp with six encodings) and benchmark families, and the similar-row results are genuinely interesting. If the dense-matrix claim were supported, this would be a notable practical advance. However, the dense benchmark design conflates density with row-similarity, so the evidence does not support the advertised 'dense matrices' contribution. The work is best read as evidence for scalability on matrices whose rows are mutually close, including near-all-ones matrices, not on arbitrary dense matrices.

major comments (2)
  1. [5.3 (Table 1), 6.2 (Fig. 3)] The 'dense' benchmark family is generated by starting from the all-ones matrix and flipping at most Cf·n entries, with Cf ≤ 1.4. For n=70 this changes at most 98 of 4900 entries (2%), so the resulting rows differ from the all-ones row in only a few positions and are nearly identical to one another. These instances are therefore a special case of the 'similar rows' class the paper itself motivates in Section 4, and the scaling in Figure 3 does not demonstrate scalability on arbitrary dense matrices, such as independent Bernoulli(0.5) matrices. Since the abstract and Section 1 claim that the frontier is pushed 'to the classes of dense matrices,' this claim outruns the evidence; the authors should either add experiments on genuinely random dense matrices or explicitly restrict the conclusion to near-all-ones / row-similar matrices.
  2. [Section 1 and Section 7] The paper's central contribution claim is that the frontier of practically efficient permanent computation is pushed to dense matrices. Yet no experiments are reported on matrices with independent random entries, and Section 7 concedes that a complete characterization of matrices admitting compact ADDs is open. Given these gaps, the broad 'dense matrices' claim is not established by the presented evidence. The revision should either provide control experiments with, e.g., Bernoulli(0.5) dense matrices, or explicitly narrow the scope of the contribution to matrices that are close (in Hamming distance) to a common row, and adjust the abstract and introduction accordingly.
minor comments (6)
  1. [Section 3] The description of Servedio and Wan's result as applying to 'matrices with at most C·n zeros' appears to be incorrect; the original result concerns matrices with at most C·n nonzeros (i.e., few ones). Please correct this to avoid misrepresenting the related work.
  2. [Section 5.2] The word 'Westemere' appears to be a typo; it should likely be 'Westmere'.
  3. [Section 6.5] The text says 'despite the density of 1s being 9n' for the instance can_61. Since 9n is a count rather than a density, the wording should be changed to 'the number of 1s being 9n'.
  4. [Section 5.1] The statement that the monolithic approach is used for dense and similar-row cases should be made explicit in the captions of Figures 3 and 5, so readers know whether the plotted times use early abstraction or not.
  5. [Section 6.6, Table 2] The row labels 'Encoding / Mode 1 2 3 4 5 6 EA Mono EA Mono' are hard to parse; please clarify which columns correspond to D4, DSharp, and the RysersADD variants.
  6. [Section 6.1, Fig. 2] The scatter plots include only instances that did not time out; this selection should be stated in the caption, as it can bias the perceived correlation between ADD size and runtime.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: RysersADD is an exact symbolic translation of Ryser's formula, with no fitted constants and no load-bearing self-citation.

full rationale

The paper's central derivation is Equation (1)/(2), an algebraic restatement of Ryser's formula; the algorithm's correctness is independent of any fitted value, and the benchmark results are not used to define the mathematical result. The only self-citation is Theorem 1 from ADDMC [20], used to justify early abstraction; this is a simple commutation lemma (∃x(f·g) = (∃x f)·g for x not in Vars(g)), externally checkable and not tailored to make the permanent results come out. The dense- and similar-row benchmark generators (Section 5.3) do raise a question of external validity—'dense' instances are all-ones matrices with at most Cf·n flips and are therefore similar-row by construction—but that concerns whether the experimental claim generalizes to arbitrary dense matrices, not whether a derived quantity collapses to an input by definition. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work to force a choice. Under the stated circularity criteria, the derivation is self-contained.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The algorithm itself introduces no free parameters and no new entities. It relies on standard mathematical facts about Ryser's formula, ADD semantics, and the early-abstraction theorem from the authors' related ADDMC work. The only assumption that is ad hoc to this paper is the use of all-ones/all-zeros base matrices with a small number of flips as proxies for the dense and sparse classes, which is the main threat to the generality of the empirical claims.

assumptions (5)
  • standard math Ryser's formula for the permanent: perm(A) = (-1)^n sum_{S subset of [n]} (-1)^|S| prod_i sum_{j in S} a_ij
    Stated in Section 2.2 and used as the foundation of the algorithm; assumed correct.
  • standard math ADD operations (product, sum, ITE, additive quantification) are implemented correctly and have the standard semantics
    The algorithm depends on these operations; the paper cites Bahar et al. [3] and does not prove them.
  • standard math Early abstraction theorem: for f:2^X -> R and g:2^Y -> R, for x in X\Y, exists x (f*g) = (exists x f)*g
    Imported as Theorem 1 from ADDMC [20] in Section 4; necessary for the incremental algorithm to avoid ADD blow-up.
  • domain assumption Sylvan library provides correct arbitrary-precision ADD operations
    The implementation relies on the correctness of this external library (Section 4.1); not verified in this paper.
  • ad hoc to paper Dense benchmarks constructed from the all-ones matrix with at most 1.4n flips are representative of the class of dense matrices
    The abstract's claim about dense matrices relies on this representativeness, which is not independently established.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Symbolic Approaches for Computing the Matrix Permanent." pith.science (2026). https://pith.science/paper/EZET4JUZ

@misc{pith2026190803252,
  author       = {Pith},
  title        = {Pith review of: On Symbolic Approaches for Computing the Matrix Permanent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EZET4JUZ}},
  note         = {Machine review of arXiv:1908.03252}
}
read the original abstract

Counting the number of perfect matchings in bipartite graphs, or equivalently computing the permanent of 0-1 matrices, is an important combinatorial problem that has been extensively studied by theoreticians and practitioners alike. The permanent is #P-Complete; hence it is unlikely that a polynomial-time algorithm exists for the problem. Researchers have therefore focused on finding tractable subclasses of matrices for permanent computation. One such subclass that has received much attention is that of sparse matrices i.e. matrices with few entries set to 1, the rest being 0. For this subclass, improved theoretical upper bounds and practically efficient algorithms have been developed. In this paper, we ask whether it is possible to go beyond sparse matrices in our quest for developing scalable techniques for the permanent, and answer this question affirmatively. Our key insight is to represent permanent computation symbolically using Algebraic Decision Diagrams (ADDs). ADD-based techniques naturally use dynamic programming, and hence avoid redundant computation through memoization. This permits exploiting the hidden structure in a large class of matrices that have so far remained beyond the reach of permanent computation techniques. The availability of sophisticated libraries implementing ADDs also makes the task of engineering practical solutions relatively straightforward. While a complete characterization of matrices admitting a compact ADD representation remains open, we provide strong experimental evidence of the effectiveness of our approach for computing the permanent, not just for sparse matrices, but also for dense matrices and for matrices with "similar" rows.

Figures

Figures reproduced from arXiv: 1908.03252 by the authors.

Figure 1
Figure 1. (a) fRS, (b) fRSP and (c) fRyser for a 4 × 4 matrix of all 1s – Step 3: Construct the Parity ADD fP AR = IT E( Ln j=1 xj , −1, +1), where L represents exclusive-or. This ADD represents the (−1)|S| term in Ryser’s formula. – Step 4: Construct fRyser = fRSP .fP AR using the product operation. Finally, we can additively quantify out all variables in fRyser and multiply the result by (−1)n to get the permanent, as given… view at source ↗
Figure 2
Figure 2. Comparison of ADD Size vs. Time taken for a subset of random benchmarks [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Performance on Dense Matrices. D4, DSharp (not shown) timeout on all in￾stances 6.2 Performance on dense matrices We plot the median running time of RysersADD and RysersADD-P against the matrix size n for dense matrices with Cf ∈ {1, 1.1, 1.2, 1.3} in [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Performance on Sparse Matrices running times of RysersADD and RysersADD-P, since D4 and DSharp were unable to solve any instance of size 30 for all 6 encodings. We observe that the running time of both the ADD-based algorithms increases with Cf . This trend continues f…
Figure 5
Figure 5. Figure 5: Performance on similar-rows matrices. D4, DSharp (not shown) timeout on all instances. 6.5 Performance on SuiteSparse Matrix Collection We report the performance of algorithms RysersADD, RysersADD-P, D4 and DSharp on 13 representative graphs from the SuiteSparse Matrix…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 61 canonical work pages

  1. [1]

    Ans ´otegui and F

    C. Ans ´otegui and F. Manya. Mapping problems with finite-domain variables to problems with boolean variables. In International Conference on Theory and Applications of Satisfia- bility Testing, pages 1–15. Springer, 2004

    work page 2004

  2. [2]

    Arora and B

    S. Arora and B. Barak. Computational Complexity: A Modern Approach . Cambridge Univ. Press, 2009

    work page 2009

  3. [3]

    Bahar, E

    R. Bahar, E. Frohm, C. Gaona, G. Hachtel, E. Macii, A. Pardo, and F. Somenzi. Algebraic decision diagrams and their applications. Journal of Formal Methods in Systems Design , 10(2/3):171–206, 1997

    work page 1997

  4. [4]

    Bahar, E

    R. Bahar, E. Frohm, C. Gaona, G. Hachtel, E. Macii, A. Pardo, and F. Somenzi. Algebraic decision diagrams and their applications. Journal of Formal Methods in Systems Design , 10(2/3):171–206, April/May 1997

    work page 1997

  5. [5]

    Bax and J

    E. Bax and J. Franklin. A permanent algorithm with exp [(n1/3/2ln (n))] expected speedup for 0-1 matrices. Algorithmica, 32(1):157–162, 2002

    work page 2002

  6. [6]

    Biere, M

    A. Biere, M. Heule, H. van Maaren, and T. Walsh. Handbook of Satisfiability: Volume 185 Frontiers in Artificial Intelligence and Applications . IOS Press, Amsterdam, The Nether- lands, The Netherlands, 2009

    work page 2009

  7. [7]

    F. Bouquet. Gestion de la dynamicit´e et ´enum´eration d’impliquants premiers: une approche fond´ee sur les Diagrammes de D´ecision Binaire. PhD thesis, Aix-Marseille 1, 1999

    work page 1999

  8. [8]

    Understanding model counting for $\beta$-acyclic CNF-formulas

    J. Brault-Baron, F. Capelli, and S. Mengel. Understanding model counting for β-acyclic CNF-formulas. arXiv preprint arXiv:1405.6043, 2014

    work page Pith review arXiv 2014

Show all 61 references
  1. [9]

    A. Z. Broder. How hard is it to marry at random?(on the approximation of the permanent). In Proceedings of the eighteenth annual ACM symposium on Theory of computing , pages 50–58. ACM, 1986

    1986

  2. [10]

    Burchard, T

    J. Burchard, T. Schubert, and B. Becker. Laissez-faire caching for parallel #SAT solving. In International Conference on Theory and Applications of Satisfiability Testing, pages 46–61. Springer, 2015

    2015

  3. [11]

    J.-Y . Cai, A. Pavan, and D. Sivakumar. On the hardness of permanent. InAnnual Symposium on Theoretical Aspects of Computer Science, pages 90–99. Springer, 1999

    1999

  4. [12]

    G. G. Cash. A fast computer algorithm for finding the permanent of adjacency matrices. Journal of mathematical chemistry, 18(2):115–119, 1995

    1995

  5. [13]

    Q. Chou, H. Liang, and F. Bai. Computing the permanental polynomial of the high level fullerene C70 with high precision. MATCH Commun. Math. Comput. Chem , 73:327–336, 2015

    2015

  6. [14]

    Courcelle

    B. Courcelle. Graph rewriting: An algebraic and logic approach. In Formal Models and Semantics, pages 193–242. Elsevier, 1990

    1990

  7. [15]

    Courcelle, J

    B. Courcelle, J. Engelfriet, and G. Rozenberg. Handle-rewriting hypergraph grammars.Jour- nal of computer and system sciences, 46(2):218–270, 1993

    1993

  8. [16]

    Courcelle, J

    B. Courcelle, J. A. Makowsky, and U. Rotics. On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathe- matics, 108(1-2):23–52, 2001

    2001

  9. [17]

    T. A. Davis and Y . Hu. The university of florida sparse matrix collection.ACM Transactions on Mathematical Software (TOMS), 38(1):1, 2011

    2011

  10. [18]

    R. Dechter. Bucket elimination: A unifying framework for reasoning. Artificial Intelligence, 113(1-2):41–85, 1999

    1999

  11. [19]

    H. Dell, T. Husfeldt, D. Marx, N. Taslaman, and M. Wahl´en. Exponential time complexity of the permanent and the tutte polynomial.ACM Transactions on Algorithms (TALG), 10(4):21, 2014. 16

    2014

  12. [20]

    J. M. Dudek, V . H. N. Phan, and M. Y . Vardi. ADDMC: Exact weighted model counting with algebraic decision diagrams. https://arxiv.org/abs/1907.05000

    1907 arXiv

  13. [21]

    Duenas-Osorio, K

    L. Duenas-Osorio, K. S. Meel, R. Paredes, and M. Y . Vardi. Counting-based reliability estimation for power-transmission grids. In AAAI, pages 4488–4494, 2017

    2017

  14. [22]

    Fujita, P

    M. Fujita, P. McGeer, and J.-Y . Yang. Multi-terminal binary decision diagrams: An efficient datastructure for matrix representation. Form. Methods Syst. Des., 10(2-3):149–169, 1997

    1997

  15. [23]

    I. P. Gent and P. Nightingale. A new encoding of alldifferent into SAT. In International Workshop on Modelling and Reformulating Constraint Satisfaction, pages 95–110, 2004

    2004

  16. [24]

    Gordon and W

    M. Gordon and W. Davison. Theory of resonance topology of fully aromatic hydrocarbons. i. The Journal of Chemical Physics, 20(3):428–435, 1952

    1952

  17. [25]

    M. Grohe. Descriptive and parameterized complexity. In International Workshop on Com- puter Science Logic, pages 14–31. Springer, 1999

    1999

  18. [26]

    J. E. Hopcroft and R. M. Karp. An nˆ5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225–231, 1973

    1973

  19. [27]

    Y . Huo, H. Liang, S.-Q. Liu, and F. Bai. Computing monomer-dimer systems through matrix permanent. Physical Review E, 77(1):016706, 2008

    2008

  20. [28]

    Ignatiev, A

    A. Ignatiev, A. Morgado, and J. Marques-Silva. PySAT: A Python toolkit for prototyping with SAT oracles. In SAT, pages 428–437, 2018

    2018

  21. [29]

    Izumi and T

    T. Izumi and T. Wadayama. A new direction for counting perfect matchings. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 591–598. IEEE, 2012

    2012

  22. [30]

    P. W. Kasteleyn. The statistics of dimers on a lattice: I. the number of dimer arrangements on a quadratic lattice. Physica, 27(12):1209–1225, 1961

    1961

  23. [31]

    D. E. Knuth. Generating all n-tuples. The Art of Computer Programming, 4, 2004

    2004

  24. [32]

    A. M. Koster, H. L. Bodlaender, and S. P. Van Hoesel. Treewidth: computational experi- ments. Electronic Notes in Discrete Mathematics, 8:54–57, 2001

    2001

  25. [33]

    H. W. Kroto, J. R. Heath, S. C. O’Brien, R. F. Curl, and R. E. Smalley. C60: Buckminster- fullerene. Nature, 318(6042):162, 1985

    1985

  26. [34]

    Lagniez and P

    J.-M. Lagniez and P. Marquis. An improved decision-dnnf compiler. In IJCAI, pages 667– 673, 2017

    2017

  27. [35]

    Liang and F

    H. Liang and F. Bai. A partially structure-preserving algorithm for the permanents of adja- cency matrices of fullerenes. Computer physics communications, 163(2):79–84, 2004

    2004

  28. [36]

    Liang, S

    H. Liang, S. Huang, and F. Bai. A hybrid algorithm for computing permanents of sparse matrices. Applied mathematics and computation, 172(2):708–716, 2006

    2006

  29. [37]

    Martins, S

    R. Martins, S. Joshi, V . Manquinho, and I. Lynce. Incremental cardinality constraints for MaxSAT. In International Conference on Principles and Practice of Constraint Program- ming, pages 531–548. Springer, 2014

    2014

  30. [38]

    Muise, S

    C. Muise, S. A. McIlraith, J. C. Beck, and E. Hsu. DSHARP: Fast d-DNNF Compilation with sharpSAT. In Canadian Conference on Artificial Intelligence, 2012

    2012

  31. [39]

    Nijenhuis and H

    A. Nijenhuis and H. S. Wilf. Combinatorial algorithms: for computers and calculators . Elsevier, 2014

    2014

  32. [40]

    Ogawa, Y

    T. Ogawa, Y . Liu, R. Hasegawa, M. Koshimura, and H. Fujita. Modulo based CNF encod- ing of cardinality constraints and its application to MaxSAT solvers. In 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, pages 9–17. IEEE, 2013

    2013

  33. [41]

    Okamoto, R

    Y . Okamoto, R. Uehara, and T. Uno. Counting the number of matchings in chordal and chordal bipartite graph classes. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 296–307. Springer, 2009

    2009

  34. [42]

    Pan and M

    G. Pan and M. Vardi. Search vs. symbolic techniques in satisfiability solving. In Proc. 7th Int’l Conf. on Theory and Applications of Satisfiability Testing (2004) , volume 3542 of Lecture Notes in Computer Science, pages 235–250. Springer, 2005. 17

    2004

  35. [43]

    Pesant, C.-G

    G. Pesant, C.-G. Quimper, and A. Zanarini. Counting-based search: Branching heuristics for constraint satisfaction problems. Journal of Artificial Intelligence Research, 43:173–210, 2012

    2012

  36. [44]

    J.-C. R ´egin. A filtering algorithm for constraints of difference in CSPs. In AAAI, volume 94, pages 362–367, 1994

    1994

  37. [45]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph minors. iii. planar tree-width. Journal of Combina- torial Theory, Series B, 36(1):49–64, 1984

    1984

  38. [46]

    D. Roth. On the hardness of approximate reasoning. Artificial Intelligence, 82(1):273–302, 1996

    1996

  39. [47]

    H. Ryser. Combinatorial mathematics, the carus mathematical monographs. Math. Assoc. Amer, 4, 1963

    1963

  40. [48]

    S. H. Sæther, J. A. Telle, and M. Vatshelle. Solving #SAT and MaxSAT by dynamic pro- gramming. Journal of Artificial Intelligence Research, 54:59–82, 2015

    2015

  41. [49]

    R. A. Servedio and A. Wan. Computing sparse permanents faster. Information Processing Letters, 96(3):89–92, 2005

    2005

  42. [50]

    C. Sinz. Towards an optimal CNF encoding of boolean cardinality constraints. In Inter- national conference on principles and practice of constraint programming, pages 827–831. Springer, 2005

    2005

  43. [51]

    F. Somenzi. CUDD package, release 2.4.1. http://vlsi.colorado.edu/˜fabio/ CUDD/

  44. [52]

    R. E. Tarjan and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on computing, 13(3):566–579, 1984

    1984

  45. [53]

    H. N. Temperley and M. E. Fisher. Dimer problem in statistical mechanics-an exact result. Philosophical Magazine, 6(68):1061–1063, 1961

    1961

  46. [54]

    S. Toda. On the computational power of PP and (+)P. In Proc. of FOCS, pages 514–519. IEEE, 1989

    1989

  47. [55]

    L. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410–421, 1979

    1979

  48. [56]

    van Dijk and J

    T. van Dijk and J. van de Pol. Sylvan: multi-core framework for decision diagrams. Interna- tional Journal on Software Tools for Technology Transfer, 19(6):675–696, 2017

    2017

  49. [57]

    Wallace, K

    C. Wallace, K. B. Korb, and H. Dai. Causal discovery via mml. In ICML, volume 96, pages 516–524, 1996

    1996

  50. [58]

    L. Wang, H. Liang, F. Bai, and Y . Huo. A load balancing strategy for parallel computation of sparse permanents. Numerical Linear Algebra with Applications, 19(6):1017–1030, 2012

    2012

  51. [59]

    Wei and S

    T.-C. Wei and S. Severini. Matrix permanent and quantum entanglement of permutation invariant states. Journal of Mathematical Physics, 51(9):092203, 2010

    2010

  52. [60]

    B. Yue, H. Liang, and F. Bai. Improved algorithms for permanent and permanental polyno- mial of sparse graph. MATCH Commun. Math. Comput. Chem, 69:831–842, 2013

    2013

  53. [61]

    Zanarini and G

    A. Zanarini and G. Pesant. Solution counting algorithms for constraint-centered search heuristics. Constraints, 14(3):392–413, 2009. 18

    2009

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.