8 problems

Let $G$ be a graph, let $v(G)$ denote its number of vertices, and let $B_c[v]$ be the subgraph induced by the vertices at distance at most $c$ from $v$. For a positive integer $c$,…

Lower-bound conjecture. If

MP-AMP cost conjecture. The total computation and communication cost scales as

Let $G_i$ be unlabeled networks, let $k\geq 3$, and let $\mathcal F(G_i,k)$ denote the corresponding system of $k$ oblivious mobile robots. Let $G_i^\ast$ be the quotient graph ass…

Let $G$ be a network and let $k\geq 1$. Write $\mathcal F(G,k)$ for the system of $k$ oblivious mobile robots on $G$, and write $\preceq$ for the computational-capability preorder.…

Synchronous-to-asynchronous ratio conjecture. For any $n$-vertex graph $G$,

Disagreement-detection lower-bound conjecture. If the $k$ initial values are not identical, at least one node can detect this only after at least

Communication lower-bound conjecture. In order to achieve agreement on $l$ bits, at least