8 problems

Linear-latency contention resolution in the GlobalClock model
arXiv@arxiv
GlobalClock contention-resolution conjecture. In the finite setting, there exists a protocol with latency $O(n)$ with high probability against an adaptive adversary. In the unbound…
Conjectureopencontention-resolution distributed-algorithms randomized-algorithms
0
Single-Nash-equilibrium convergence conjecture for decentralized fictitious play
arXiv@arxiv
Let $\{f_t\}_{t\geq 1}$ be the sequence of joint empirical frequencies generated by decentralized fictitious play (DFP) in a near-potential game, and let $C_{N\delta}$ denote the s…
Conjectureopendistributed-algorithms fictitious-play game-theory
0
Efficient deterministic fractional coloring for sparse high-girth graphs
arXiv@arxiv
A graph has a $(a:b)$ -coloring if each vertex receives a set of $b$ colors from a palette of $a$ colors, with adjacent vertices receiving disjoint sets. Let $k\geqslant 2$ and $q$ …
Conjectureopendistributed-algorithms fractional-coloring graph-coloring
0
Equivalence of almost finiteness and distributed almost finiteness
arXiv@arxiv
Equivalence conjecture. A class $\mathcal{G}$ is almost finite if and only if it is distributed almost finite.
Conjectureopenalmost-finiteness distributed-algorithms graph-limits
1
Impossibility of distributed algorithms for TP under limited communication constraints
arXiv@arxiv
Impossibility claim. Given these communication constraints, there exists no distributed algorithm that can solve TP without further conditions on the sequence of communication grap…
Conjectureopenconsensus distributed-algorithms time-varying-digraphs
0
The conjecture on the near-maximal step count of Semi-SMER
arXiv@arxiv
Near-maximal step-count conjecture. For “almost every” $n\geq 4$ ,
Conjectureopendistributed-algorithms number-theory prime-sieving
1
Definitive consensus conjecture for graph-supported linear updates
arXiv@arxiv
Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a connected graph on $N$ vertices. Let $\mathbf{1}$ be the column vector of ones, and let $D(\mathcal{G})$ denote the number of synch…
Conjectureopenconsensus-dynamics distributed-algorithms graph-theory
1
Convergence of the modified iterative water-filling algorithm for weighted sum-rate maximization
arXiv@arxiv
Consider the modified iterative water-filling algorithm in which each user repeatedly solves the priced subproblem … subject to its power constraint, and the interference prices…
Conjectureopendistributed-algorithms interference-channels optimization
0