Efficiency--Complexity Tradeoff and Constrained Percolation
Abstract
We study the efficiency--complexity tradeoff for resource-limited agents through directed first-passage percolation. Nonnegative i.i.d. edge weights represent physical energy expenditure, while the logarithmic size of a constrained path family measures representational complexity. For translation-invariant families, a path-joining property yields deterministic large-distance costs in rational directions and joint convexity in constraint parameter and direction, under suitable moment and feasibility assumptions. Our main result concerns the limiting cost parameterized by path-family entropy. Using techniques from analytic combinatorics in several variables (ACSV), we establish its almost-sure existence and joint continuity in entropy and direction for nested families satisfying additional generating-function conditions, on the corresponding entropy range. Path-count asymptotics supply the change of parameter linking this cost to the constraint-parameterized cost. Two planar examples constrain the number of turns or the number of East-runs of length at least two.
Related
- Salt stress shifts wild tomato root systems toward transport efficiency along a gravitropism-constrained Pareto front
- A growth-maintenance tradeoff determines nutrient-limited growth in phytoplankton
- Split suppression gene drives reveal a design tradeoff between inheritance and reproductive load in Aedes aegypti
- Environmental stress and phenotypic tradeoff modulate the adaptive potential of novel coding sequences for de novo gene birth
- Altered connectivity and network efficiency in preterm infants
BibTeX
@misc{baryshnikov2026efficiencycomplexity,
title = {{Efficiency--Complexity Tradeoff and Constrained Percolation}},
author = {Yuliy Baryshnikov and Efe Onaran},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33864},
eprint = {2610.33864},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33864},
}
RIS
TY - UNPB
TI - Efficiency--Complexity Tradeoff and Constrained Percolation
AU - Yuliy Baryshnikov
AU - Efe Onaran
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33864
UR - https://arxiv.org/abs/2610.33864
AB - We study the efficiency--complexity tradeoff for resource-limited agents through directed first-passage percolation. Nonnegative i.i.d. edge weights represent physical energy expenditure, while the logarithmic size of a constrained path family measures representational complexity. For translation-invariant families, a path-joining property yields deterministic large-distance costs in rational directions and joint convexity in constraint parameter and direction, under suitable moment and feasibility assumptions. Our main result concerns the limiting cost parameterized by path-family entropy. Using techniques from analytic combinatorics in several variables (ACSV), we establish its almost-sure existence and joint continuity in entropy and direction for nested families satisfying additional generating-function conditions, on the corresponding entropy range. Path-count asymptotics supply the change of parameter linking this cost to the constraint-parameterized cost. Two planar examples constrain the number of turns or the number of East-runs of length at least two.
ER -