# On the Volume Complexity of LCLs*

Will Rosenbaum
Max Planck Institute for Informatics

Jukka Suomela
Aalto University

## Overview

1. LCLs in the LOCAL Model
2. Query Model and Volume Complexity
3. Complexity Landscape for Volume
4. Open(?) Questions

# I. LCLs in the LOCAL Model

## Context

• consider family graphs $\mathcal{G}$ with maximum degree at most $\Delta$ (constant)
• an instance is a graph $G \in \mathcal{G}$ with a vertex labeling $\mathcal{L}$ from a finite alphabet
• want to find a valid output labeling $\mathcal{L}'$ that solves problem $\Pi$ on input $(G, \mathcal{L})$
• $\Pi$ is a locally checkable labeling problem (LCL) if a solution is globally valid $\iff$ it is valid on an $O(1)$ neighborhood of each node
• e.g., $k$ coloring, maximal matching, maximal independent set,...
• LOCAL model: in $T$ rounds, every node sees its distance $T$ neighborhood

# II. Query Model and Volume Complexity

## Query Model

• each $v \in V$ represents a processor
• $v$ maintains set $V_v$ of visited nodes, initially $V_v = \{v\}$
• $v$ adaptively queries $G$
• for $u \in V_v$, $\mathrm{query}(u, j)$ returns
• identity, input, and degree of $u$'s $j$th neighbor $w$
• $w$'s random bits (for randomized algorithms)
• $v$ sets $V_v \leftarrow V_v \cup \{w\}$

Volume of algorithm $A$: maximum $|V_v|$ over all nodes $v$, graphs, inputs on $n$ nodes

Note. similar to LCA model

## Questions

What are the possible volume complexities of LCL problems?

How are volume and distance complexities related?

What is the role of randomness in the volume model?

# III. Main Results: Volume Complexity Landscape

## Preliminary Observations

Observation 1. If $\Pi$ has round complexity $T(n)$ in the LOCAL model, then its volume complexity $R(n)$ satisfies $$T(n) \leq R(n) \leq \Delta^{O(T(n))}$$

## Summary of Results: New Classes

Problem R-DIST D-DIST R-VOL D-VOL
LeafColoring $\Theta(\log n)$ $\Theta(\log n)$ $\Theta(\log n)$ $\Theta(n)$
BalancedTree $\Theta(\log n)$ $\Theta(\log n)$ $\Theta(n)$ $\Theta(n)$
Hier-THC($k$) $\Theta(n^{1/k})$ $\Theta(n^{1/k})$ $\tilde\Theta(n^{1/k})$ $\tilde\Theta(n)$
Hybrid-THC($k$) $\Theta(\log n)$ $\Theta(\log n)$ $\tilde\Theta(n^{1/k})$ $\tilde\Theta(n)$
HH-THC($k$, $\ell$) $\Theta(n^{1/\ell})$ $\Theta(n^{1/\ell})$ $\tilde\Theta(n^{1/k})$ $\tilde\Theta(n)$

## LeafColoring

• Input: each $v \in V$ gets
• parent $P(v)$, left child $LC(v)$, right child $RC(v)$
(port #s or $\perp$)
• input color $\chi_{\mathrm{in}}(v) \in \{R, B\}$
• Output: a color $\chi_{\mathrm{out}}(v) \in \{R, B\}$
• Validity: Call $v$ internal if port labels are pair-wise distinct and $v = P(RC(v)) = P(LC(v))$.
• $v$ not internal $\implies$ $\chi_{\mathrm{out}}(v) = \chi_{\mathrm{in}}(v)$
• $v$ internal $\implies$ $\chi_{\mathrm{out}}(v) \in \{\chi_{\mathrm{out}}(RC(v)), \chi_{\mathrm{out}}(LC(v))\}$

## LeafColoring Example

Input graph, port numbers shown for vertex $v$

Input labeling and induced pseudo-forest ($P(v) = 4$, $LC(v) = 1$, $RC(v) = 3$)

Valid output labeling

## Analysis of LeafColoring

• Algorithm:
• each internal $v$ uses private randomness to choose a child
• follow path of "chosen children" to a leaf *
• output color of leaf
• W.H.P. all paths to leaves are of length $O(\log n)$
• $\Omega(\log n)$ distance is necessary to see leaf
• $\Omega(n)$ volume is necessary for deterministic algorithms

* have to deal with cycles, but whatever

## BalancedTree

• Input: each $v \in V$ gets
• parent $P(v)$, left child $LC(v)$, right child $RC(v)$
(port #s or $\perp$)
• left neighbor $LN(v)$, right neighbor $RN(v)$
• Output: $(X, P)$ where $X \in \{B, U\}$ (balanced/unbalanced), $P$ is port number
• Compatibility: $v \in V$ is compatible if some locally checkable conditions on input labeling are satisfied
• all nodes compatible $\iff$ parent/child edges form balanced binary tree $+$ "lateral" edges
• Validity:
• $v$ not compatible $\implies$ $v$ outputs $(U, \perp)$
• compatible "leaves" output $(B, P(v))$
• internal nodes output $(B, P(v))$ $\iff$ both children do
• internal nodes output $(U, \cdot)$ where $\cdot$ is child outputting $(U, \cdot)$
• Global Interpretation:
• if all nodes $v$ output $(B, P(v))$, then parent/child edges form a balanced binary tree with compatible lateral edges
• if some node $v$ is incompatible, then all ancestors of $v$ output $(U, \cdot)$

## Analysis of BalancedTree

• for each $v$, suffices to see all descendants within distance $d(v, w)$ where $w$ is nearest leaf below $v$
• $\implies O(\log n)$ distance suffices
• for root of balanced binary tree, must examine all leaves to find incompatible node
• $\implies \Omega(n)$ volume necessary

# IV. Open(?) Questions

## More Complexity Classes?

1. Are there LCLs with deterministic volume complexity in $\omega(\log^* n) \cap o(n)$?
2. Are there LCLs with randomized volume complexity in $\Omega(\log \log n) \cap o(\log n)$?
• What is the (randomized) volume complexity of Sinkless Orientation?
3. Are there LCLs with randomized volume complexity $\sim n^{\alpha}$ for $\alpha \neq 1/k$?

## Type of Randomness?

Could consider (at least) $3$ types of randomness:

• public randomness all nodes have access to same random string (e.g. LCAs)
• private randomness each node has own independent random string
• querying $v$ reveals $v$'s randomness
• secret randomness each node has own independent random string
• querying $v$ does not reveal $v$'s randomness

Question. What is the relative power of these random models?

## Complexity with Limited Bandwidth?

Question.What do complexity classes look like in CONGEST model?

• in each round, nodes can send $B (= O(\log n))$ bit messages to each neighbor
• preliminary observations in our paper

Question. Is there an LCL with volume complexity $R(n)$ and CONGEST complexity $\Delta^{\Omega(R(n))}$?

full paper here