Compression
Particles following a local stochastic rule must gather into a configuration with small perimeter.
Problem statement and measuresexpand
Starting connected, the \(n\) particles perform a Markov chain (at each step one particle, chosen at random, proposes a move and accepts it with a probability that depends only on its neighbourhood) with bias \(\lambda\) towards having more neighbours. The system is \(\alpha\)-compressed if its perimeter is at most \(\alpha\) times the minimum possible.
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.