We consider an undirected graph $G=(V,E)$ and a fault budget $f$. An edge‑fault‑tolerant connectivity labeling scheme assigns short labels to vertices and edges such that, for any vertex pair $(s,t)$ and any failed edge set $F\subseteq E$ with $|F|\le f$, the connectivity of $s$ and $t$ in $G-F$ can be answered by looking only at the labels of $s$, $t$ and the edges in $F$. We present a scheme whose labels are $O(\log^{2} n)$ bits long and can be computed in deterministic polynomial time. This improves the previous deterministic bound $\tilde{O}(\sqrt{f})$ by Long, Pettie, and Saranurak\'25, and even slightly beats the randomized bound $O(\min\{f+\log n,\;\log^{2} n\log f\})$ of Dory & Parter\'21 and Long et al. when $f = \Omega(\log^{2} n)$. Moreover, for arbitrary $f$, it is the first scheme that achieves $\tilde{O}(1)$‑size labels while being correct for all queries simultaneously. The approach merges the cycle‑space labeling of Dory and Parter with a recent sparse cycle basis result by Knauer\'26, yielding a compact representation and efficient query processing.
Review: This result pushes the deterministic edge‑fault‑tolerant connectivity labeling frontier close to optimal, offering a practically computable solution that could inspire robust network monitoring tools.