Search papers, labs, and topics across Lattice.
This paper identifies a black-box workload barrier for achieving exact girth in the CONGEST model using multi-scale nearest-source estimation. By employing adaptive source cardinalities and capacities, the authors derive a workload bound that reveals the necessary expected retained-source workload for constant exactness probability. The findings indicate that achieving exact girth requires significant computational resources, specifically an expected workload of \(\Omega(n_t/\log n_t)\), highlighting the limitations of current methods in this area.
Achieving exact girth in CONGEST requires a staggering expected workload that scales with the logarithm of the number of vertices, challenging the efficiency of existing multi-scale methods.
Recent multi-scale nearest-source methods give polynomially sublinear girth approximations in CONGEST. We isolate the direct black-box route for making this framework exact: sequential calls to the same estimator on fresh exchangeable source sets, with source cardinalities and nearest-source capacities chosen adaptively from previous scalar outputs and with an adaptive stopping rule. On a bounded-degree, logarithmic-diameter family $H_t$ with $n_t$ vertices and a unique girth-$g_t=\Theta(\log n_t)$ cycle, exactness requires a sampled cycle source to survive at an antipodal edge despite a linear number of strictly closer competitors. For any such exactification $\mathcal A$, a permutation-rank argument yields the implementation-independent workload bound $\Pr[\mathcal A(H_t)=g_t]\leq(3g_t/n_t)\,\mathbb E[\sum_{j=1}^{T}\min\{Q_j,k_j\}]$, where $T$ is the number of executed calls, $Q_j$ is the source-set cardinality, and $k_j$ is the nearest-source capacity of call $j$. Thus constant exactness probability requires $\Omega(n_t/g_t)=\Omega(n_t/\log n_t)$ expected retained-source workload. We formally show that retuning the recent multi-scale template solely through its scale count/order, Bernoulli or fixed-cardinality sampling, capacities, and scalar-output stopping rules lies in this class. For the standard sequential packetized estimator realization, the workload theorem gives an $\Omega(n_t/\log n_t)$ expected-round corollary. This is a barrier to a defined black-box exactification strategy, not a lower bound for unrestricted exact girth in CONGEST.
