On Function-Correcting Codes

A class of codes designed to protect function evaluations of a message from errors was introduced in “Function-Correcting Codes” by Lenz et al. 2023. They provide a graphical representation for the problem of constructing functioncorrecting codes. We use this graph to get a lower bound on the redundancy required for function correction and classical error correction. For linear functions, we show that the adjacency matrix of this graph is diagonalised by tensor powers of Discrete Fourier Transform (DFT) matrices, which leads to a lower bound on redundancy. Also, we propose a version of the sphere packing bound for linear-function correcting codes. Further more, we identify a class of linear functions for which an upper bound proposed by Lenz et al., is tight.