Source-linked AI summary
A Tight Second-Order Lower Bound for Routing Labels in Trees
Hanqing Li
TL;DR
Designer-port routing labels must let a decoder recover the first path port from two vertex labels, but prior bounds left the squared log-log overhead unresolved. We prove a matching lower bound, establishing the optimal worst-case length up to constant factors.
Problem
The prior lower bound was log n + Ω(log log n), below the log n + O((log log n)^2) upper bound, leaving open whether the squared term is necessary.
Source: §1 · p. 1Method
The proof fixes a decoder and label universe, constructs incompatible child-size capacity demands, and uses random hard subtrees plus probability amplification.
Source: §1 · p. 1Results
The optimal worst-case label length is log n + Θ((log log n)^2) for designer-port routing in rooted n-vertex trees.
Source: §1 · p. 1Takeaways & Limitations
The second-order term in the optimal worst-case label length is determined up to constant factors.
Source: §1 · p. 1The proof is nonconstructive at the level of a single explicit hard tree and gives no lower bound on query time.
Source: §5 · p. 6
Abstract
from arXiv · showhide
In the designer-port routing-labeling problem, every vertex of a rooted tree receives a binary label and the child edges receive distinct port numbers. Given only the labels of a source and a destination, a decoder must return the first port on their path. Gawrychowski, Janczewski, and Lopuszanski gave labels of length $\log_2 n+O((\log_2\log_2 n)^2)$, whereas the previous lower bound was $\log_2 n+\Omega(\log_2\log_2 n)$. We prove that every scheme for all $n$-vertex trees needs a label of length $\log_2 n+\Omega((\log_2\log_2 n)^2)$ for every sufficiently large $n$. The result allows arbitrary port assignments and imposes no computational restriction on either the encoder or the decoder. Thus the second-order term in the optimal worst-case label length is determined up to constant factors.
1 Introduction
The paper resolves whether the squared log-log overhead is necessary for designer-port routing labels. Its lower bound matches the existing upper bound in the second-order term, even without computational or port-assignment restrictions.
1 Introduction
- The lower bound holds without restrictions on encoding time, decoding time, or the choice of port numbers.The theorem applies to some tree and vertex for every sufficiently large n.Source: §1 · p. 1
- The optimal worst-case label length is log n + Θ((log log n)^2) for designer-port routing in rooted n-vertex trees.The lower bound holds for every sufficiently large n and, combined with the cited upper bound, determines the second-order term up to constant factors.Source: §1 · p. 1
- The proof fixes a decoder and label universe, then uses incompatible child-size capacity demands and random hard subtrees to bound successful labelings.A second distribution amplifies the failure probability enough to union-bound over root labels and port assignments.Source: §1 · p. 1
2 Label universes and two induction statements
The section formalizes routing labelings and the label-universe embedding question. It sets up two inductive distributional statements, using disjoint port classes to constrain which labels can serve each child subtree.
2 Label universes and two induction statements
- A correct labeling assigns each vertex a finite binary string and gives each child a distinct port; the decoder uses only source and destination labels to return the first path port.For a fixed root label, destination labels are partitioned by the decoder’s output port.Source: §2 · p. 2
- In any correctly labeled tree, vertex labels are pairwise distinct, and each child subtree’s labels must lie in its root’s corresponding port class.The classes for different ports are disjoint.Source: §2 · p. 2
- For sufficiently large sizes, d(s) increases strictly with s and is a constant multiple of s within each dyadic size level.The construction chooses θ last; the stated monotonicity holds for fixed constants and sufficiently large m.Source: §2 · p. 2
- For every positive s, distributions W_s and R_s are specified independently of the decoder and label set, and the proof constructs them inductively in sequence.It builds R_s from smaller W_b distributions, then W_s from smaller R_b distributions, avoiding circular dependence.Source: §2 · p. 2
3 Amplifying the embedding failure
The section constructs a distribution of trees whose many child subtrees impose incompatible port-capacity demands. A deficit argument and probability amplification make successful embeddings unlikely even after accounting for root labels and port assignments.
3 Amplifying the embedding failure
- For sufficiently large m, the distribution R_s has the embedding-failure property stated in Lemma 5.The construction chooses k distinct child sizes, attaches independent W_b trees beneath a branching vertex, and uses a unary chain for leftover vertices.Source: §3 · pp. 2–3
- For a fixed root label and child-to-port assignment, disjoint port classes force at least ξ_m k/4 child subtrees to have capacity below their demand.This follows from a total positive deficit of at least ξ_m A_s/2 and an upper bound of 2A_s/k on each deficit.Source: §3 · p. 3
- The deficient child subtrees embed jointly with probability bounded using the independent weak induction statements.The passage states this bound but does not provide its expression.Source: §3 · p. 3
- The union bound over root labels and port assignments gives total success probability at most e^(-m^2), and the unary chain cannot increase it.The exponent dominates the union-bound cost and m^2.Source: §3 · p. 3
4 Equal-mass profiles with separated demands
The section constructs decoder-independent child-size profiles whose codewords preserve equal mass while producing separated demand vectors. A large binary code supplies many such profiles, with common size and level masses.
4 Equal-mass profiles with separated demands
- The construction depends only on m, not on the decoder or label set, and adjusts to each n ∈ [2m, 2m+1) with one further child of fixed size.Source: §4 · pp. 3–4
- The profiles encode bits in pairs of child sizes with opposite signs, keeping each pair’s total size independent of its bit.Source: §4 · p. 3
- Every profile has positive integer child sizes in [Hℓ, 2Hℓ), strictly decreasing in displayed order, with a common child count, total n−1, and level masses.Source: §4 · p. 4
- The code C contains at least 240m codewords with minimum Hamming distance B/4, where B = Θ(m/κ).Source: §4 · p. 4
- For distinct codewords, the sorted child-size vectors are separated: flipping a bit changes the L1 size vector by 2Nℓδℓ, and the code distance yields K²B/m² = Ω(κ(log m)²/m).Source: §4 · p. 4
5 The weak distribution and proof of the lower bound
The section closes the induction by comparing child-size profiles with root-label port capacities, then uses the resulting distribution bounds to prove a second-order label-length lower bound.
5 The weak distribution and proof of the lower bound
- W_n samples a codeword profile and independently attaches an R_{s_j(z)} tree below each child, so the strong induction applies to every child.Lemma 8 states that W_n satisfies (1).Source: §5 · p. 5
- A root label covers at most one codeword profile, bounding the probability that any label in S covers the random profile by |S|/|C|.For profiles not covered by a given label, a deficient child-port pair and the strong induction bound the embedding probability; the union argument allows adaptive port numbering.Source: §5 · pp. 5–6
- L ≥ log n + ε(log log n)^2 − O(1) for sufficiently large n, establishing the lower bound for schemes whose labels share a bounded universe.The argument applies regardless of port assignment.Source: §5 · p. 6
- Theorem 2 follows by combining this lower-bound result with the known upper bound [1].Source: §5 · p. 6
- The proof is nonconstructive for an individual hard tree and gives no lower bound on query time.Its distributional induction statements still cover decoders chosen separately for each n.Source: §5 · p. 6