🔢 mathematics

Is star complexity a proxy for information based complexity of graphs?

This paper empirically investigates the hypothesis that Information-Based Complexity (IBC) measures for graphs are asymptotically equivalent by comparing a link-based IBC measure with star complexity and its related measure ${\cal C}^*$ , finding a strong correlation between them and identifying an easily computable upper bound for star complexity.

Original authors: Russell K. Standish

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Russell K. Standish

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant box of LEGO bricks. You want to know how "complicated" a specific structure built from those bricks is. Is it a simple tower, or is it a sprawling, intricate castle?

This paper asks a big question: Can we measure the complexity of a shape (specifically, a network of dots and lines called a "graph") in two different ways, and will those two ways tell us the same story?

Here is the breakdown of the paper's journey, explained simply:

1. The Two Ways to Measure Complexity

The author, Russell Standish, is comparing two different "rulers" for measuring complexity.

Ruler A: The "Universal Translator" (Information-Based Complexity)
Think of this as a super-smart librarian. If you give the librarian a description of a LEGO castle, they try to find the shortest possible sentence that uniquely describes that castle.

If the castle is simple, the sentence is short.
If the castle is weird and unique, the sentence is long.
The Catch: To do this perfectly, the librarian has to check every possible sentence to see which ones describe the same castle. This takes a massive amount of time and computer power, so we can only do it for very small castles (like 10 or 22 dots).

Ruler B: The "Star Builder" (Star Complexity)
This is a different way of building. Imagine you have a special tool called a "Star." A star is just one central dot connected to everything else around it.

To build a complex shape, you start with a few stars and either glue them together (Union) or cut away parts (Intersection).
Star Complexity is simply counting how many times you had to glue or cut to build your shape.
The Catch: This is easy to count, but it's not a "Universal Translator" in the strict mathematical sense. It's just a count of operations.

2. The Big Question

The paper asks: If we use the "Star Builder" method, does it actually measure the same thing as the "Universal Translator"?

In other words, if a shape is hard to describe with words (high complexity), is it also hard to build with stars (high star complexity)?

3. The Experiment: Small Castles vs. Giant Cities

The author tried to compare these two rulers, but there was a problem: The "Universal Translator" is so slow that it can only handle tiny shapes (10 or 22 dots). The "Star Builder" is fast, but we needed to see if they agreed on the small ones before trusting them on big ones.

The Small Test (10 and 22 dots):
The author built thousands of tiny shapes and measured them with both rulers.

The Result: On these tiny shapes, the two rulers didn't seem to agree very well. The correlation was weak. It was like trying to compare a stopwatch to a sundial on a cloudy day; the results were messy.

The "Shortcut" Trick:
Since the "Universal Translator" is too slow for big shapes, the author invented a shortcut. Instead of finding the perfect way to build a shape with stars, they found an easy way to build it that might use a few extra steps.

Think of it like taking a slightly longer route to work. It's not the fastest route, but it's a very good estimate of how far away work is.
The author proved that this "shortcut" estimate is almost always the same as the real "Star Builder" count.

The Big Test (1,000 dots):
Now, the author used this "shortcut" ruler on 1,000 random, giant shapes (which are too big for the "Universal Translator" to handle).

The Result: When they compared the "Universal Translator" (on the small shapes) with the "Shortcut Star Ruler" (on the big shapes), they found a strong relationship.
Even though the math wasn't a perfect straight line, the trend was clear: Shapes that are hard to describe are also hard to build with stars.

4. The Conclusion

The paper concludes that yes, "Star Complexity" is a good proxy for the more complex "Information-Based Complexity."

The Analogy:
Imagine you want to know how "unique" a person is.

Method A: You ask a super-intelligent AI to write a biography that no one else shares. (Hard to do, takes forever).
Method B: You count how many unique hobbies that person has. (Easy to do).

This paper says: "Even though we can't always ask the AI (Method A) for big groups of people, counting the unique hobbies (Method B) gives us a very good idea of how unique they are."

Summary:
The author showed that while the two methods look different on paper, they are actually measuring the same underlying "complexity" of a shape. The "Star Builder" method is a practical, easy-to-calculate tool that tells us the same story as the much harder, theoretical "Universal Translator."

Technical Summary: Star Complexity as a Proxy for Information-Based Complexity of Graphs

Problem Statement
The paper investigates whether "star complexity," a structural measure of graphs, serves as a practical proxy for "Information-Based Complexity" (IBC). IBC is a formal complexity measure defined by the proportion of descriptions in a specific language that map to a given object via a classifier. While theoretical IBC (based on universal Turing machines) is asymptotically independent of the encoding language, the paper hypothesizes that practical IBC measures derived from different encoding schemes will also be asymptotically equivalent. Specifically, the study compares a standard graph IBC measure ( $C$ ), which encodes graphs via edge lists and classifies them by automorphism, against star complexity, which defines complexity based on the minimum number of union and intersection operations of elementary "stars" required to construct a graph.

Methodology
The research employs a comparative empirical approach using two distinct complexity measures:

Graph Complexity ( $C$ ): Calculated using the formula $C(x) = \ell - \log_2 \omega(x)$ , where $\ell$ is the length of the edge-list encoding and $\omega$ is the number of strings of that length mapping to the same graph (determined via graph automorphism algorithms using the Nauty library).
Star Complexity ($Star(G)$): Defined as the minimal number of set operations (union/intersection) of elementary stars (a hub vertex connected to all others) needed to generate a graph.
Star-Based IBC ( $C^*$ ): An IBC measure derived specifically from star complexity. It encodes the graph by storing the vertex count, star count, and a Reverse Polish Notation (RPN) "recipe" of operations. $C^*$ adjusts the bit-length of this recipe by subtracting $\log_2 \omega$ , where $\omega$ represents the number of equivalent recipes for a given graph.
Upper Bound Estimation ( $\overline{Star}(G)$ ): Since computing the exact $Star(G)$ requires an exhaustive search of all possible operation sequences (which is computationally infeasible for large graphs), the authors introduce an algorithmic upper bound. This algorithm constructs a graph by covering maximum-degree vertices with stars and covering remaining edges via pairwise intersections, then optimizes the expression using set associativity.

Experimental Execution
The study utilized the EcoLab package, optimized for GPU execution (Intel Xe graphics) to achieve a 23x speedup over single-threaded CPU processing. The experiments involved:

Small-Scale Exhaustive Search: Generating all graphs with 10 and 22 vertices having a star complexity of 8 or less. This allowed for the exact calculation of $C$ , $Star(G)$, and $C^*$ , including the enumeration of equivalent recipes ( $\omega$ ).
Large-Scale Sampling: Generating 1,000 Erdős-Rényi random graphs with 1,000 vertices to test the relationship between the easily computable upper bound $\overline{Star}(G)$ and the standard complexity $C$ .

Key Results

Small Graphs (10 and 22 vertices): The correlation between the standard complexity $C$ and raw star complexity $Star(G)$ was found to be negligible (correlation coefficients $\rho \approx 0.08$ and $-0.04$, respectively). Similarly, the correlation between $C$ and the star-derived IBC $C^*$ was weak ( $\rho \approx 0.14$ and near zero).
Correlation of Measures: However, $Star(G)$ and $C^*$ showed a moderate positive correlation ( $\rho \approx 0.6$ ), and the estimated upper bound $\overline{Star}(G)$ was strongly correlated with the exact $Star(G) $($ \rho \approx 0.85$).
Large Graphs (1,000 vertices): The most significant finding emerged from the large-scale sampling. A strong, albeit non-linear, relationship was observed between the computable upper bound $\overline{Star}(G)$ and the information-based complexity $C$ .

Significance and Claims
The paper concludes that while raw star complexity does not linearly correlate with information-based complexity on small, exhaustive datasets, the two measures are likely measuring the same underlying property for larger graphs. The strong empirical relationship between the easily computable upper bound of star complexity and the standard IBC measure ( $C$ ) suggests that star complexity acts as a valid proxy for information-based complexity in practical scenarios. The authors posit that this supports the broader hypothesis that different practical IBC encoding schemes are asymptotically equivalent. Consequently, star complexity, being more computationally tractable than full IBC calculations for large graphs, can serve as a reliable estimator for graph complexity.

1. The Two Ways to Measure Complexity

2. The Big Question

3. The Experiment: Small Castles vs. Giant Cities

4. The Conclusion

More like this