Property Testing of Computational Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917132940345344 |
|---|---|
| author | Czumaj, Artur Sohler, Christian |
| author_facet | Czumaj, Artur Sohler, Christian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_07577 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Property Testing of Computational Networks Czumaj, Artur Sohler, Christian Data Structures and Algorithms 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. |
| title | Property Testing of Computational Networks |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.07577 |