Pith. sign in

REVIEW 2 minor 49 references

Planar Perfect Matching Counting is as Hard as Determinants

T0 review · 0 major / 2 minor · reviewed 2026-06-28 · grok-4.3

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

Pith's one-line read Counting perfect matchings in planar graphs requires Ω(n^{ω/2}) arithmetic operations over algebraic circuits.

desk verdict This paper gives a matching lower bound showing planar perfect matching counting requires Ω(n^{ω/2}) operations in algebraic circuits, confirming optimality of the FKT+Yuster algorithm even on grids. read the letter →

arxiv 2606.03975 v1 pith:ORZDG5RD submitted 2026-06-02 cs.CC cs.DMcs.DS

Radu Curticapean , Jiaheng Wang This is my paper · ORCID
classification cs.CCcs.DMcs.DS
keywords planargraphsperfectmatchingsalgebraiccircuitslowerboundsmatrixmultiplicationexponentFKTalgorithmcountingproblemsgrid
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 proves a matching lower bound for the problem of counting perfect matchings in edge-weighted planar graphs on n vertices: no algebraic circuit or comparably strong model can solve it with O(n^{ω/2 - ε}) operations. This bound is tight against the known upper bound of Õ(n^{ω/2}) obtained by combining the FKT algorithm with Yuster's matrix-multiplication technique. The hardness persists even when the input is restricted to square grids. A reader would care because the result shows that the existing algorithm cannot be improved in its dependence on the matrix-multiplication exponent ω.

What carries the argument

Algebraic-circuit lower bound obtained by reduction from determinant computation, showing that planar perfect-matching counting is at least as hard as determinants up to the square-root exponent.

What would settle it

An explicit algebraic circuit that counts perfect matchings in n-vertex planar graphs (including grids) using o(n^{ω/2}) arithmetic operations would falsify the claim.

Watch

Extended reading notes

Core claim

Over algebraic circuits and other sufficiently strong computational models, the number of perfect matchings in an edge-weighted n-vertex planar graph cannot be computed in O(n^{ω/2 - ε}) arithmetic operations for any ε > 0. The bound holds even for square-grid inputs and matches the complexity of Yuster's algorithm up to polylog factors.

Load-bearing premise

The lower bound applies inside algebraic circuit models and other sufficiently strong computational models.

Editorial extensions

If this is right

  • Yuster's algorithm is optimal for counting perfect matchings in planar graphs under algebraic circuits.
  • No asymptotically faster algorithm exists even when the graph is a square grid.
  • The exponent ω/2 is the exact complexity threshold for this counting problem in the stated models.
  • Any improvement in matrix multiplication immediately yields a matching improvement for planar perfect matching counting.

Reading between the lines

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

  • The result suggests that planar perfect matching counting and determinant computation are equivalent in algebraic complexity up to quadratic blow-up in input size.
  • Similar lower bounds may apply to other Holant problems that reduce to planar matching counting.
  • If weaker circuit models admit faster algorithms, the gap would isolate exactly where the hardness originates.
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, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The manuscript proves a conditional lower bound showing that counting edge-weighted perfect matchings in n-vertex planar graphs (including square grids) requires Ω(n^{ω/2}) arithmetic operations in algebraic circuit models and other sufficiently strong models. The proof proceeds by reduction from determinant computation, establishing that any O(n^{ω/2-ε}) algorithm for planar PM counting would yield a faster determinant algorithm, thereby matching the upper bound obtained by combining the FKT algorithm with Yuster's O(n^{ω/2}) procedure.

Significance. If the reduction is correct, the result is significant because it confirms the optimality of the best known algorithm for this problem and rules out faster algorithms even in restricted cases such as grids. The approach of reducing from determinant computation (rather than an ad-hoc assumption) supplies a concrete, falsifiable link to a well-studied problem and strengthens the complexity landscape for planar counting and holographic algorithms.

minor comments (2)
  1. [Abstract] Abstract, paragraph 2: the qualifier “other sufficiently strong computational models” should be given an explicit definition or pointer to the model class used in the reduction (e.g., algebraic circuits of polynomial size).
  2. [Main theorem] The reduction’s size blow-up and the precise arithmetic cost of the constructed planar instance should be stated with explicit constants or big-O factors in the main theorem statement so that the exponent ω/2 is visibly preserved.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and their recommendation to accept. We are pleased that the significance of the conditional lower bound and its connection to determinant computation is recognized.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The paper derives its lower bound for planar perfect matching counting via an explicit reduction from determinant computation (an external algebraic problem whose complexity is independent of the present work). The upper bound references the external FKT algorithm and Yuster's algorithm, while the matching lower bound is obtained by size-blowup reduction showing that fast planar PM counting would yield faster determinant evaluation in algebraic circuits. No equation or claim reduces by construction to a quantity defined inside the paper, no parameter is fitted and then renamed as a prediction, and no load-bearing step relies on a self-citation chain. The derivation is therefore self-contained against external benchmarks.

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

Abstract-only review provides no concrete information on free parameters, axioms, or invented entities used in the proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Planar Perfect Matching Counting is as Hard as Determinants." pith.science (2026). https://pith.science/paper/ORZDG5RD

@misc{pith2026260603975,
  author       = {Pith},
  title        = {Pith review of: Planar Perfect Matching Counting is as Hard as Determinants},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ORZDG5RD}},
  note         = {Machine review of arXiv:2606.03975}
}
abstract

In the 1960s, Fisher, Kasteleyn and Temperley designed an ingenious algorithm for computing the partition function of the dimer model, or equivalently, for counting perfect matchings in edge-weighted planar graphs (Philos. Mag. 1961; J. Mathematical Phys. 1963). This FKT algorithm later became the foundation for Valiant's holographic algorithms (FOCS 2004; SIAM J. Comput. 2008), which motivated the study of counting problems under the Holant framework. Combined with an algorithm by Yuster (FOCS 2008), the FKT algorithm allows us to count edge-weighted perfect matchings in planar $n$-vertex graphs with $\tilde{O}(n^{\omega/2})$ arithmetic operations, where $\omega<2.372$ is the matrix multiplication exponent. We prove a corresponding lower bound: Over algebraic circuits and other sufficiently strong computational models, perfect matchings in edge-weighted $n$-vertex planar graphs $G$ cannot be counted in $O(n^{\omega/2-\epsilon})$ arithmetic operations. This confirms the optimality of Yuster's algorithm. Our bound holds even when $G$ is an edge-weighted square grid.

Figures

Figures reproduced from arXiv: 2606.03975 by the authors.

Figure 1
Figure 1. A blue diamond indicates a marshaller. Orange lines indicate light beams. The [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The planar H-gadget. 2. Baur and Strassen established ωMM ≤ ωDET by computing the partial derivatives together with the original function, and then applying Cramer’s Rule [BS83]. However, the relation between matrix multiplication and matrix determinant is not known beyond algebraic models, e.g., in terms of bit complexity. It is worth remarking that Yuster’s algorithm runs in O(n ωMM/2+1 ) bit operations. Remark. T… view at source ↗
Figure 3
Figure 3. Computing the weight of the H-gadget in different states. Cases not shown here have no internal perfect matching. Lemma 5. The weight of an H-gadget is 1, if H is , or , −1, if H is , x, if H is , and 0, if H is invalid. Proof. For assignments a of odd Hamming weight, the graph H − S has an odd number of vertices and thus no perfect matching, so the weight of H under a is zero. This leaves 8 cases to consider. Among… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: The gadget Hj,πi is in state iff (i, j) forms an inversion, i.e., i < j and πi > πj. The left part shows an inversion, the right part shows a non-inversion. 3. For all i ∈ [m − 1] and j ∈ [m], join the b-edge of Hi,j with the t-edge of Hi+1,j . 4. For all i ∈ [m], intr…
Figure 5
Figure 5. Figure 5: A grid embedding of the graph GX, where X is a 4-by-4 matrix. Proof. The mapping φ ∶ (i, j) ↦ (j, πi) clearly is a bijection [m] 2 → [m] 2 . We show that φ is a bijection between inversions in π and gadgets in τ . (See also [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: Replacing an edge uv of weight w ≠ 1 with gadget Mk for k = (w − 1) −1 over Fp. Proof of Theorem 1. Assume ω = ωDET > 2, as the statement holds vacuously otherwise. Suppose there is an algorithm A that solves #PlanarPM in time O(n ω/2−ϵ ) for ϵ > 0. Given A ∈ F m×m, co…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 1 canonical work pages

  1. [1]

    A full dichotomy for Holant ^ c , inspired by quantum computation

    Miriam Backens. A full dichotomy for Holant ^ c , inspired by quantum computation. SIAM J. Comput. , 50(6):1739--1799, 2021

    2021

  2. [2]

    Rodney J. Baxter. Exactly Solved Models in Statistical Mechanics . Academic press limited London , 1982

    1982

  3. [3]

    Beyond bilinear complexity: What works and what breaks with many modes? Electron

    Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Ian Orzel, Tim Seppelt, and Jiaheng Wang. Beyond bilinear complexity: What works and what breaks with many modes? Electron. Colloquium Comput. Complex. , TR26-025 , 2026. To appear in CCC 2026

    2026

  4. [4]

    Berkowitz

    Stuart J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inf. Process. Lett. , 18(3):147--150, 1984

    1984

  5. [5]

    Bunch and John E

    James R. Bunch and John E. Hopcroft. Triangular factorization and inversion by fast matrix multiplication. Math. Comp. , 28:231--236, 1974

    1974

  6. [6]

    The complexity of partial derivatives

    Walter Baur and Volker Strassen. The complexity of partial derivatives. Theor. Comput. Sci. , 22:317--330, 1983

    1983

  7. [7]

    [Can88a] John Canny.The complexity of robot motion planning, volume 1987 ofACM Doctoral Dissertation Awards

    Peter B \" u rgisser. Completeness classes in algebraic complexity theory. CoRR , abs/2406.06217, 2024

    work page arXiv 2024

  8. [8]

    Some results on matchgates and holographic algorithms

    Jin - yi Cai and Vinay Choudhary. Some results on matchgates and holographic algorithms. Int. J. Softw. Informatics , 1(1):3--36, 2007

    2007

Show all 49 references
  1. [9]

    Complexity dichotomies for counting problems

    Jin-Yi Cai and Xi Chen. Complexity dichotomies for counting problems. V ol. 1 . Cambridge University Press, Cambridge, 2017. Boolean domain

    2017

  2. [10]

    On the theory of matchgate computations

    Jin - yi Cai, Vinay Choudhary, and Pinyan Lu. On the theory of matchgate computations. Theory Comput. Syst. , 45(1):108--132, 2009

    2009

  3. [11]

    Holographic algorithm with matchgates is universal for planar \# csp over boolean domain

    Jin - Yi Cai and Zhiguo Fu. Holographic algorithm with matchgates is universal for planar \# csp over boolean domain. SIAM J. Comput. , 51(2):17--50, 2022

    2022

  4. [12]

    FKT is not universal - A planar H olant dichotomy for symmetric constraints

    Jin - Yi Cai, Zhiguo Fu, Heng Guo, and Tyson Williams. FKT is not universal - A planar H olant dichotomy for symmetric constraints. Theory Comput. Syst. , 66(1):143--308, 2022

    2022

  5. [13]

    Matchgates revisited

    Jin - Yi Cai and Aaron Gorenstein. Matchgates revisited. Theory Comput. , 10:167--197, 2014

    2014

  6. [14]

    Holographic algorithms: From art to science

    Jin - yi Cai and Pinyan Lu. Holographic algorithms: From art to science. J. Comput. Syst. Sci. , 77(1):41--61, 2011

    2011

  7. [15]

    Werner, and Freek Witteveen

    Matthias Christandl, Vladimir Lysikov, Vincent Steffan, Albert H. Werner, and Freek Witteveen. The resource theory of tensor networks. Quantum , 8:1560, December 2024

    2024

  8. [16]

    Dichotomy for H olant\( ^ \( _ \) \) problems on the boolean domain

    Jin - Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for H olant\( ^ \( _ \) \) problems on the boolean domain. Theory Comput. Syst. , 64(8):1362--1391, 2020

    2020

  9. [17]

    Parameterizing the permanent: Hardness for fixed excluded minors

    Radu Curticapean and Mingji Xia. Parameterizing the permanent: Hardness for fixed excluded minors. In Karl Bringmann and Timothy M. Chan, editors, 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022 , pages 297--307. SIAM , 2022

    2022

  10. [18]

    Paths, trees, and flowers

    Jack Edmonds. Paths, trees, and flowers. Canadian J. Math. , 17:449--467, 1965

    1965

  11. [19]

    Evenbly and G

    G. Evenbly and G. Vidal. Tensor network renormalization. Phys. Rev. Lett. , 115:180405, Oct 2015

    2015

  12. [20]

    On the expressive power of planar perfect matching and permanents of bounded treewidth matrices

    Uffe Flarup, Pascal Koiran, and Laurent Lyaudet. On the expressive power of planar perfect matching and permanents of bounded treewidth matrices. In Takeshi Tokuyama, editor, Algorithms and Computation, 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2...

    2007

  13. [21]

    Nested dissection of a regular finite element mesh

    Alan George. Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. , 10:345--363, 1973

    1973

  14. [22]

    A dichotomy for real weighted H olant problems

    Sangxia Huang and Pinyan Lu. A dichotomy for real weighted H olant problems. Comput. Complex. , 25(1):255--304, 2016

    2016

  15. [23]

    Towards quantum machine learning with tensor networks

    William Huggins, Piyush Patil, Bradley Mitchell, K Birgitta Whaley, and E Miles Stoudenmire. Towards quantum machine learning with tensor networks. Quantum Science and Technology , 4(2):024001, Jan 2019

    2019

  16. [24]

    On the complexity of k- SAT

    Russell Impagliazzo and Ramamohan Paturi. On the complexity of k- SAT . J. Comput. Syst. Sci. , 62(2):367--375, 2001

    2001

  17. [25]

    Jaeger, D

    F. Jaeger, D. L. Vertigan, and D. J. A. Welsh. On the computational complexity of the J ones and T utte polynomials. Math. Proc. Cambridge Philos. Soc. , 108(1):35--53, 1990

    1990

  18. [26]

    P. W. Kasteleyn. Dimer statistics and phase transitions. J. Mathematical Phys. , 4:287--293, 1963

    1963

  19. [27]

    Kaltofen and Pascal Koiran

    Erich L. Kaltofen and Pascal Koiran. Expressing a fraction of two determinants as a determinant. In J. Rafael Sendra and Laureano Gonz \' a lez - Vega, editors, Symbolic and Algebraic Computation, International Symposium, ISSAC 2008, Linz/Hagenberg, Austria, July 20-23, 2008, ...

    2008

  20. [28]

    Lipton, Donald J

    Richard J. Lipton, Donald J. Rose, and Robert Endre Tarjan. Generalized nested dissection. SIAM J. Numer. Anal. , 16(2):346--358, 1979

    1979

  21. [29]

    Characterizing V aliant's algebraic complexity classes

    Guillaume Malod and Natacha Portier. Characterizing V aliant's algebraic complexity classes. J. Complex. , 24(1):16--38, 2008

    2008

  22. [30]

    Maximum matchings in planar graphs via gaussian elimination

    Marcin Mucha and Piotr Sankowski. Maximum matchings in planar graphs via gaussian elimination. Algorithmica , 45(1):3--20, 2006

    2006

  23. [31]

    Meena Mahajan and V. Vinay. Determinant: Combinatorics, algorithms, and complexity. Chic. J. Theor. Comput. Sci. , 1997, 1997

    1997

  24. [32]

    P. A. Samuelson. A method of determining explicitly the coefficients of the characteristic equation. Ann. Math. Statistics , 13:424--429, 1942

    1942

  25. [33]

    A dichotomy for real boolean H olant problems

    Shuai Shao and Jin - Yi Cai. A dichotomy for real boolean H olant problems. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020 , pages 1091--1102. IEEE , 2020

    2020

  26. [34]

    Partial and total matrix multiplication

    Arnold Sch \" o nhage. Partial and total matrix multiplication. SIAM J. Comput. , 10(3):434--455, 1981

    1981

  27. [35]

    Gaussian elimination is not optimal

    Volker Strassen. Gaussian elimination is not optimal. Numer. Math. , 13:354--356, 1969

    1969

  28. [36]

    H. N. V. Temperley and Michael E. Fisher. Dimer problem in statistical mechanics---an exact result. Philos. Mag. (8) , 6:1061--1063, 1961

    1961

  29. [37]

    Classes of arithmetic circuits capturing the complexity of computing the determinant

    Seinosuke Toda. Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Transactions on Information and Systems , 75(1):116--124, 1992

    1992

  30. [38]

    Leslie G. Valiant. Completeness classes in algebra. In Michael J. Fischer, Richard A. DeMillo, Nancy A. Lynch, Walter A. Burkhard, and Alfred V. Aho, editors, Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA , pa...

    1979

  31. [39]

    Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput. , 8(3):410--421, 1979

    1979

  32. [40]

    Leslie G. Valiant. Expressiveness of matchgates. Theor. Comput. Sci. , 289(1):457--471, 2002

    2002

  33. [41]

    Leslie G. Valiant. Quantum circuits that can be simulated classically in polynomial time. SIAM J. Comput. , 31(4):1229--1254, 2002

    2002

  34. [42]

    Leslie G. Valiant. Accidental algorithms. In 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, Berkeley, California, USA, October 21-24, 2006, Proceedings , pages 509--517. IEEE Computer Society, 2006

    2006

  35. [43]

    Leslie G. Valiant. Holographic algorithms. SIAM J. Comput. , 37(5):1565--1594, 2008

    2008

  36. [44]

    Ryan Williams

    Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. J. ACM , 65(5):27:1--27:38, 2018

    2018

  37. [45]

    Complexity: Knots, Colourings and Countings

    Dominic Welsh. Complexity: Knots, Colourings and Countings . London Mathematical Society Lecture Note Series. Cambridge University Press, 1993

    1993

  38. [46]

    Determinant algorithms for random planar structures

    David Bruce Wilson. Determinant algorithms for random planar structures. In Michael E. Saks, editor, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana, USA , pages 258--267. ACM/SIAM , 1997

    1997

  39. [47]

    Ryan Williams

    R. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. SIAM J. Comput. , 47(5):1965--1985, 2018

    1965

  40. [48]

    Matrix sparsification for rank and determinant computations via nested dissection

    Raphael Yuster. Matrix sparsification for rank and determinant computations via nested dissection. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, USA, October 25-28, 2008 , pages 137--145. IEEE Computer Society, 2008

    2008

  41. [49]

    Maximum matching in graphs with an excluded minor

    Raphael Yuster and Uri Zwick. Maximum matching in graphs with an excluded minor. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007...

    2007

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.