Bridging
Particles moving between two sites must build a bridge across a gap that balances path length against bridge cost.
Problem statement and measuresexpand
Particles occupy a path between two fixed sites across a gap in the terrain. They run a local Markov chain that rewards neighbours and penalises particles over the gap. The system should form a shortcut bridge whose length and cost are balanced, with high probability in the stationary distribution.
Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).
Progress map
tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Moves
unknown
\(\text{eventually}\) vs —
unknown
— vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.