pith. sign in

arxiv: 2604.16327 · v1 · submitted 2026-03-09 · 💻 cs.CC

An improved upper bound measure of star complexity of graphs

Russell K. Standish This is my paper

Pith reviewed 2026-05-15 14:24 UTC · model grok-4.3

classification 💻 cs.CC
keywords star complexitycircuit complexitygraph complexityinformation complexitylogic circuit optimizationErdős-Renyi graphsupper bounds
0
0 comments X

The pith

A tighter upper bound on star complexity from logic circuit optimization produces a more linear relationship with information complexity.

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

This paper refines a proxy upper bound for star complexity of graphs by using the ABC logic circuit optimizer instead of an earlier looser estimate. The author corrects the graph walking algorithm to target the circuit complexity version rather than formula complexity, then tests the new measure on 1000 random 500-vertex graphs. A sympathetic reader would care because star complexity measures the computational resources needed to recognize graph properties, and tighter practical bounds could improve predictions of how graph structure affects circuit size. The work shows that the refined measure yields a visibly straighter correlation with information-based complexity measures.

Core claim

Exploiting the ABC package for logic circuit optimization supplies a strictly tighter upper bound on the circuit complexity variant of star complexity. When this bound is computed for 1000 Erdős-Renyi graphs on 500 vertices, the relationship to information-based complexity becomes more linear than with the previous proxy.

What carries the argument

ABC-based circuit optimization bound, which estimates the minimum logic circuit size needed to represent the graph and thereby upper-bounds its star complexity.

If this is right

  • Star complexity of graphs can be bounded more tightly by repurposing existing logic-circuit optimizers.
  • The relationship between star complexity and information-based complexity is closer to linear once the circuit variant is measured correctly.
  • Numerical estimation of star complexity becomes feasible for graphs with hundreds of vertices.
  • The distinction between circuit and formula complexity matters for the observed linearity in these measures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same optimizer-driven approach might be tested on other random-graph ensembles or on structured graphs to check whether linearity persists.
  • If the bound remains useful, it could serve as a practical surrogate when exact star complexity is intractable.
  • Hybrid measures that combine ABC bounds with information-theoretic quantities might further tighten estimates of computational cost.

Load-bearing premise

The ABC package produces a valid and strictly tighter upper bound on the circuit complexity of the graphs, and the modified graph walking algorithm accurately captures the circuit complexity variant rather than formula complexity.

What would settle it

Applying the new ABC-based measure to the same 1000 graphs and obtaining a correlation with information complexity that is no more linear than the earlier proxy, or finding concrete graphs where the bound exceeds the true star complexity.

Figures

Figures reproduced from arXiv: 2604.16327 by Russell K. Standish.

Figure 1
Figure 1. Figure 1: Plot of Star and StarABC against C for 1000 Erdös-Renyi randomly generated graphs of 500 vertices each. 4. StarABC versus C of randomly generated Erdös-Renyi graphs We repeat the experiment outlined in [1], generating 1000 500-vertex Erdös-Renyi graphs (instead of the 1000-vertex graphs generated in [1]), and computing C, the im￾proved Star and StarABC. The results can be seen in figure ER-500. As expected… view at source ↗
read the original abstract

In \cite{Standish25c}, I explored the connection between star complexity and information based complexity. Because of the numerical difficulty in computing star complexity, I introduced a proxy measure that is an upper bound to star complexity, and showed a strong albeit non-linear relationship between the measures. In this paper, I introduce a tighter upper bound, by exploiting the well-known ABC package used to optimise logic circuits. In testing the new measure, I found that I had been computing the {\em formula complexity} variant of star complexity, rather than the tighter {\em circuit complexity} variant. Since Jukna clearly states the connection between star complexity and circuit complexity, I have modified the graph walking algorithm to capture circuit complexity rather than formula complexity. With this new ABC-based measure, applied to a set of 1000 500 vertex Erd\"os-Renyi graphs, a more linear relationship between star complexity and information based complexity is found.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 0 minor

Summary. The manuscript claims to introduce a tighter upper bound on star complexity of graphs by integrating the ABC logic circuit optimization package, corrects the prior proxy (which computed formula complexity) by modifying the graph-walking algorithm to target the circuit complexity variant with gate sharing, and reports a more linear empirical relationship with information-based complexity when evaluated on 1000 Erdős-Rényi graphs of 500 vertices.

Significance. If the ABC integration produces a rigorously valid and strictly tighter upper bound and the algorithm modification correctly enforces sharing while remaining an upper bound on star-cover size, the work supplies a practical, scalable proxy that strengthens the observed link between star complexity and information complexity, facilitating further empirical and theoretical study of these measures on large graphs.

major comments (3)
  1. [Abstract] Abstract and method description: the assertion that the graph-walking algorithm was modified to capture circuit complexity (with sharing) rather than formula complexity is not accompanied by any pseudocode, precise description of the change, or small-graph validation showing how reuse is now permitted while still upper-bounding star-cover size; without this, it is impossible to confirm the new numbers are closer to circuit complexity.
  2. [Method] ABC integration: no details are supplied on how ABC-optimized circuits are converted into the numerical upper bound on star complexity, nor is any argument or small-instance comparison given establishing that the bound is strictly tighter than the previous proxy and remains a valid upper bound.
  3. [Results] Empirical results: the claim of a 'more linear relationship' on the 1000 graphs lacks quantitative support (e.g., correlation coefficients or R² values before versus after the change) and does not reference any table or figure that would allow assessment of the improvement.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive comments. We address each major point below and will revise the manuscript to provide the requested details, descriptions, and quantitative support.

read point-by-point responses

  1. Referee: [Abstract] Abstract and method description: the assertion that the graph-walking algorithm was modified to capture circuit complexity (with sharing) rather than formula complexity is not accompanied by any pseudocode, precise description of the change, or small-graph validation showing how reuse is now permitted while still upper-bounding star-cover size; without this, it is impossible to confirm the new numbers are closer to circuit complexity.

    Authors: We agree that the current description of the algorithm modification is insufficient. In the revised manuscript we will add a precise textual description of the changes that enable gate sharing, include pseudocode for the updated graph-walking procedure, and provide a small-graph example that demonstrates permitted reuse while preserving the upper-bound property on star-cover size. revision: yes

  2. Referee: [Method] ABC integration: no details are supplied on how ABC-optimized circuits are converted into the numerical upper bound on star complexity, nor is any argument or small-instance comparison given establishing that the bound is strictly tighter than the previous proxy and remains a valid upper bound.

    Authors: We acknowledge the omission. The revision will expand the method section with a step-by-step account of how ABC-optimized circuits are mapped to the numerical upper-bound value, supply a short argument establishing strict improvement over the prior proxy, and include explicit small-instance comparisons confirming both tightness and continued validity as an upper bound. revision: yes

  3. Referee: [Results] Empirical results: the claim of a 'more linear relationship' on the 1000 graphs lacks quantitative support (e.g., correlation coefficients or R² values before versus after the change) and does not reference any table or figure that would allow assessment of the improvement.

    Authors: The referee correctly notes the absence of quantitative metrics. We will add correlation coefficients and R² values comparing the pre- and post-change relationships, and will insert explicit references to the supporting tables and figures in the results text. revision: yes

Circularity Check

0 steps flagged

No significant circularity; empirical linearity is observational

full rationale

The paper's central result is an empirical observation: applying an external ABC-based upper-bound proxy (distinct from the author's prior proxy) to 1000 random graphs yields a more linear relationship with information-based complexity. The modification to the graph-walking algorithm is asserted without equations or self-referential derivation that would force the outcome by construction. No step reduces a claimed prediction to a fitted parameter or to a self-citation chain; the relationship is tested on fresh data rather than being tautological. Self-citation to the author's earlier work supports only the historical context, not the new bound or linearity claim.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No explicit free parameters, axioms, or invented entities are stated in the abstract; the bound relies on the external ABC optimizer and the author's graph algorithm.

pith-pipeline@v0.9.0 · 5479 in / 925 out tokens · 40345 ms · 2026-05-15T14:24:55.117003+00:00 · methodology

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

13 extracted references · 13 canonical work pages · 1 internal anchor

  1. [2]

    To use it, we used the C API to create a single-valued logic function with n boolean inputs, where n is the number of vertices

    ABC optimised star complexity upper bound, StarABC (G) ABC is a package for optimisation and validation of logic circuits[ 8,9]. To use it, we used the C API to create a single-valued logic function with n boolean inputs, where n is the number of vertices. Initially , this was seeded with the or of all stars covered by the graph, and the remaining edges i...

    work page

  2. [4]

    The results can be seen in figure ER-500

    StarABC versus C of randomly generated Erdös-Renyi graphs We repeat the experiment outlined in [ 1], generating 1000 500-vertex Erdös-Renyi graphs (instead of the 1000-vertex graphs generated in [ 1]), and computing C, the im- proved Star and StarABC . The results can be seen in figure ER-500. As expected, StarABC is a much tighter upper bound than the ori...

    work page

  3. [5]

    Conclusion In this paper, we explore estimating star complexity of graphs by means of the ABC package, widely used for optimising electronic logic circuits. It proves to be a more accu- rate estimate of star complexity than the proposal in [ 1], and also demonstrates an even stronger relationship between star complexity and information based complexity

    work page

  4. [6]

    Standish, R.K. Is star complexity a proxy for information based complexity of graphs? In Proceedings of the Complex Networks & Their Applications XIV; Cherifi, H.; Rocha, L.M.; Cherifi, C.; Ertem, M.Z., Eds. Springer Cham, 2026, Studies in Computational Intelligence. http://www.arxiv .org/abs/2510.07722

    work page internal anchor Pith review arXiv 2026

  5. [7]

    On Complexity and Emergence

    Standish, R.K. On Complexity and Emergence. Complexity International 2001, 9. arXiv:nlin.AO/0101006

    work page arXiv 2001

  6. [8]

    Li, M.; Vitányi, P .An Introduction to Kolmogorov Complexity and its Applications, 2nd ed.; Springer: New York, 1997

    work page 1997

  7. [9]

    Complexity of Networks

    Standish, R.K. Complexity of Networks. In Proceedings of the Recent Advances in Artificial Life; Abbass.; et al., Eds., Singapore, 2005; V ol. 3, Advances in Natural Computation , pp. 253–263. arXiv:cs.IT/0508075

    work page arXiv 2005

  8. [10]

    Entropy and the complexity of graphs: III

    Mowshowitz, A. Entropy and the complexity of graphs: III. Graphs with prescribed informa- tion content. Bulletin of Mathematical Biology 1968, 30, 387–414

    work page 1968

  9. [11]

    Entropy and the Complexity of Graphs: IV

    Mowshowitz, A. Entropy and the Complexity of Graphs: IV. Entropy Measures and Graphical Structure. Bulletin of Mathematical Biology 1968, 30, 533–546

    work page 1968

  10. [13]

    ABC: An academic industrial-strength verification tool

    Brayton, R.; Mishchenko, A. ABC: An academic industrial-strength verification tool. In Pro- ceedings of the International Conference on Computer Aided V erification. Springer, 2010, pp. 24–40

    work page 2010

  11. [14]

    FPGA technology mapping with adaptive gate decomposition

    Fan, L.; Wu, C. FPGA technology mapping with adaptive gate decomposition. In Proceedings of the Proceedings of the 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays, 2023, pp. 135–140

    work page 2023

  12. [15]

    DAG-aware synthesis orchestration

    Li, Y .; Liu, M.; Ren, H.; Mishchenko, A.; Yu, C. DAG-aware synthesis orchestration. IEEE T ransactions on Computer-Aided Design of Integrated Circuits and Systems 2024, 43, 4666–4675

    work page 2024

  13. [16]

    A Note on the Validity of Cross-Validation for Evaluating Autoregressive Time Series Prediction.Comput

    Standish, R.K. StarComplexity2. https://osf.io/ypxk8/. https://doi.org/10.3390/1010000

    work page doi:10.3390/1010000