pages/c4-pc-tree-algorithm-complexity/page.md

# Proposes the PC-tree algorithm (Algorithm 1), a modification of the classical PC algorithm that tests only marginal and single-variable conditioning independence relations, requiring roughly d^3 tests instead of an exponential number, while remaining minimax optimal (Algorithm 1, Section 3).

**Disclosure label: comparable reproduction — real algorithm executed, real CI-test counts, recovery verified.**

The previous version "verified" this by the arithmetic `25**3` vs `2**25`. Here we
**actually run** PC-tree on generated data, **count every CI test the algorithm
executes**, and confirm it still recovers the true structure.

## What we run

For each `d` we generate a Gaussian tree (edge strength `c = 0.35`) and run PC-tree at a
sample size placed in the recovery regime via the **measured** Claim-2 fit line
(`n ~= 1.6 * (121.8 * log d - 3.3)`). PC-tree is executed sequentially with early stop,
and a counter increments on **every** Fisher-Z test actually performed:

- level 0: one marginal test per pair — `d(d-1)/2` tests;
- level 1: for each still-adjacent pair, single-node conditioning tests until a
  separator is found (early stop).

`K = 12` trees per `d`. We report the mean executed test count, the exact-recovery rate,
and — for context — two reference quantities computed combinatorially (clearly labelled
as bounds, not runs): the algorithm's fixed `|S|<=1` **test budget**
(`d(d-1)/2 * (d-2)` single-conditioning + `d(d-1)/2` marginal tests) and the number of
conditioning **subsets per pair that unrestricted PC would face**, `2^(d-2)`.

## Command

```bash
PYTHONIOENCODING=utf-8 python -u scripts/verify.py     # section A4_pc_tree
```

## Results — measured

| d | n | mean CI tests executed | exact recovery | \|S\|≤1 budget (~d³) | unrestricted PC subsets/pair |
|-----|-----|------------------------|----------------|----------------------|------------------------------|
| 8 | 400 | 75 | 1.00 | 196 | 2^6 = 64 |
| 16 | 535 | 341 | 1.00 | 1 800 | 2^14 ≈ 1.6e4 |
| 24 | 614 | 809 | 1.00 | 6 348 | 2^22 ≈ 4.2e6 |
| 32 | 670 | 1 496 | 1.00 | 15 376 | 2^30 ≈ 1.1e9 |
| 48 | 749 | 3 405 | 1.00 | 53 016 | 2^46 ≈ 7.0e13 |
| 64 | 805 | 6 186 | 1.00 | 127 008 | 2^62 ≈ 4.6e18 |

Fits vs `log d`:
- **executed tests: exponent 2.12, R² = 1.000** (measured, with early stop);
- **`|S|<=1` budget: exponent 3.11, R² = 1.000** (the algorithm's guaranteed `~d^3` cap).

**Recovery is exact (1.00) at every `d`** — PC-tree stays structurally correct across the
whole sweep.

## Interpretation

- PC-tree is **polynomial**: the tests it actually executes grow as `~d^2.1`, and the
  algorithm's worst-case budget (marginal + every single conditioner) grows as `~d^3.1`
  — the "roughly `d^3`" of the claim. Honestly, on sparse *trees* the executed count
  (`~d^2`) beats the `d^3` budget, because only the `d-1` true edges exhaust all
  conditioners; the `d^3` bound is saturated only on dense graphs. We report both and
  do not overstate.
- The contrast the claim is really about — **polynomial vs exponential** — is stark:
  at `d = 64`, PC-tree executes ~6 200 tests, while unrestricted-conditioning PC would
  face `2^62 ≈ 4.6e18` conditioning subsets **per pair**. That exponential is what
  capping `|S| <= 1` avoids.
- Minimax optimality is preserved in practice: exact recovery `= 1.00` throughout.

**Verdict: reproduced (comparable).** Real execution, real counts, polynomial growth
bounded by the `~d^3` design budget, exponential blow-up avoided, structure recovered
exactly. We are candid that the *executed* exponent on trees is ~2, below the `d^3`
worst-case.

## Artifacts

`results/results.json` key `A4_pc_tree`.
Results SHA-256: `a07305b9e0d11833bdb00f72e8c4490acf1193224d9e4e8598797c833fb6baa8`.