FPRD LabShare an approach

← Claims

Literature calibration

MMR-035

Claim MMR-035

Exact statement

Peak-memory DAG scheduling is the weighted one-shot black-pebbling problem, and one-shot pebbling has strong hardness results.

StatusEstablished in cited literature and retained as calibration
External reviewThe cited result appears in external literature; that publication is not external review of the FPRD synthesis.

Context

This result belongs to the reconstruction from algebraic matrix-multiplication certificates to explicit arithmetic dependency DAGs and their resource receipts.

Hypotheses and scope

  • All resource conclusions are restricted to the arithmetic, storage, fan-out, coefficient, and precision models named in the source record.

Proof or evidence

Jin et al., arXiv:2312.13526; Austrin–Pitassi–Wu, arXiv:1109.4910. Run 4 is positioned as classical state-space DP plus an interface factorization.

Mathematical overview and evidence boundary →

Verification notes

The bibliography retains the primary-source attribution. The public record does not treat publication of the underlying theorem as review of this FPRD synthesis.

Limitations

  • The record does not improve the known matrix-multiplication exponent and does not imply that omega equals two.
  • Construction bounds are not optimality, communication, I/O, or hardware claims unless the exact statement says so.

Open work

Confirm the primary citation, hypotheses, and exact scope through an independent source audit.