{"ID":2831712,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.07577","arxiv_id":"2512.07577","title":"Property Testing of Computational Networks","abstract":"In this paper we initiate the study of \\emph{property testing of weighted computational networks viewed as computational devices}. Our goal is to design property testing algorithms that for a given computational network with oracle access to the weights of the network, accept (with probability at least $\\frac23$) any network that computes a certain function (or a function with a certain property) and reject (with probability at least $\\frac23$) any network that is \\emph{far} from computing the function (or any function with the given property). We parameterize the notion of being far and want to reject networks that are \\emph{$(ε,δ)$-far}, which means that one needs to change an $ε$-fraction of the description of the network to obtain a network that computes a function that differs in at most a $δ$-fraction of inputs from the desired function (or any function with a given property). To exemplify our framework, we present a case study involving simple neural Boolean networks with ReLU activation function. As a highlight, we demonstrate that for such networks, any near constant function is testable in query complexity independent of the network's size. We also show that a similar result cannot be achieved in a natural generalization of the distribution-free model to our setting, and also in a related vanilla testing model.","short_abstract":"In this paper we initiate the study of \\emph{property testing of weighted computational networks viewed as computational devices}. Our goal is to design property testing algorithms that for a given computational network with oracle access to the weights of the network, accept (with probability at least $\\frac23$) any n...","url_abs":"https://arxiv.org/abs/2512.07577","url_pdf":"https://arxiv.org/pdf/2512.07577v1","authors":"[\"Artur Czumaj\",\"Christian Sohler\"]","published":"2025-12-08T14:12:57Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}