Pith. sign in

REVIEW 2 minor 49 references

Counting perfect matchings in planar graphs requires Ω(n^{ω/2}) arithmetic operations over algebraic circuits.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.3

2026-06-28 07:10 UTC pith:ORZDG5RD

load-bearing objection 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.

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

Planar Perfect Matching Counting is as Hard as Determinants

Radu Curticapean , Jiaheng Wang This is my paper
classification cs.CC cs.DMcs.DS
keywords planar graphsperfect matchingsalgebraic circuitslower boundsmatrix multiplication exponentFKT algorithmcounting problemsgrid graphs
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

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 ω.

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.

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.

Load-bearing premise

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

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 this falsifier — get emailed when new claim-graph text bears on it.

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.

Where Pith is reading between the lines

These are 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.

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

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

pith-pipeline@v0.9.1-grok · 5747 in / 954 out tokens · 29175 ms · 2026-06-28T07:10:48.142211+00:00 · methodology

0 comments
read the original 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 Jiaheng Wang, Radu Curticapean.

Figure 1
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. 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.… view at source ↗
Figure 3
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 consi… view at source ↗
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], introduce a fresh single-edge gadget, and join its dangling edge with the ℓ-edge of Hi,1. Perform the same for t-edge of H1,j , for all j ∈ [m].… view at source ↗
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] view at source ↗
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, construct the graph GA obtained from Theorem 3 by substituting xij = aij . Then pm(GA) = det(A), and running A on GA outputs det(A) in time O(… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

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

  9. [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

  10. [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

  11. [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

  12. [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

  13. [13]

    Matchgates revisited

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

    2014

  14. [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

  15. [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

  16. [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

  17. [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

  18. [18]

    Paths, trees, and flowers

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

    1965

  19. [19]

    Evenbly and G

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

    2015

  20. [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, 2007, Proceedings , volume 4835 of Lecture Notes in Computer Science , pages 124-...

    2007

  21. [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

  22. [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

  23. [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

  24. [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

  25. [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

  26. [26]

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

    1963

  27. [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, Proceedings , pages 141--146. ACM , 2008

    2008

  28. [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

  29. [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

  30. [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

  31. [31]

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

    1997

  32. [32]

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

    1942

  33. [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

  34. [34]

    Partial and total matrix multiplication

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

    1981

  35. [35]

    Gaussian elimination is not optimal

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

    1969

  36. [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

  37. [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

  38. [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 , pages 249--261. ACM , 1979

    1979

  39. [39]

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

    1979

  40. [40]

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

    2002

  41. [41]

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

    2002

  42. [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

  43. [43]

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

    2008

  44. [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

  45. [45]

    Complexity: Knots, Colourings and Countings

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

    1993

  46. [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

  47. [47]

    Ryan Williams

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

    1965

  48. [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

  49. [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 , pages 108--117. SIAM , 2007

    2007