  The \emph{$f$-fault-tolerant connectivity labeling} ($f$-FTC labeling) is a
scheme of assigning each vertex and edge with a small-size label such that one
can determine the connectivity of two vertices $s$ and $t$ under the presence
of at most $f$ faulty edges only from the labels of $s$, $t$, and the faulty
edges. This paper presents a new deterministic $f$-FTC labeling scheme
attaining $O(f^2 \mathrm{polylog}(n))$-bit label size and a polynomial
construction time, which settles the open problem left by Dory and Parter
[PODC'21]. The key ingredient of our construction is to develop a deterministic
counterpart of the graph sketch technique by Ahn, Guha, and McGreger [SODA'12],
via some natural connection with the theory of error-correcting codes. This
technique removes one major obstacle in de-randomizing the Dory-Parter scheme.
The whole scheme is obtained by combining this technique with a new
deterministic graph sparsification algorithm derived from the seminal
$\epsilon$-net theory, which is also of independent interest. As byproducts,
our result deduces the first deterministic fault-tolerant approximate distance
labeling scheme with a non-trivial performance guarantee and an improved
deterministic fault-tolerant compact routing. The authors believe that our new
technique is potentially useful in the future exploration of more efficient FTC
labeling schemes and other related applications based on graph sketches.
