2026-09-10T09:45:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27782 2026-09-09T12:19:38Z ddc:004 open_access

Property Testing of Computational Networks Czumaj, Artur Sohler, Christian Property Testing Testing Computational Networks In this paper we initiate the study of 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 2/3) any network that computes a certain function (or a function with a certain property) and reject (with probability at least 2/3) any network that is 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 (ε,δ)-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. While the analysis of neural Boolean networks with ReLU activation function is rigorous and technically demanding, we consider it a testament to the robustness of our framework and the depth of our findings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Artur Czumaj and Christian Sohler 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.65 urn:nbn:de:0030-drops-277827 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.65 eng https://creativecommons.org/licenses/by/4.0/legalcode