%Aigaion2 BibTeX export from Idiap Publications
%Friday 05 December 2025 04:45:55 PM

@ARTICLE{Mayo98a1,
                      author = {Mayoraz, Eddy},
                    projects = {Idiap},
                       title = {On the Complexity of Recognizing Regions Computable by Two-Layered Perceptrons},
                     journal = {Annals Mathematics and Artificial Intelligence},
                        year = {1999},
                    crossref = {mayo98a},
                    abstract = {This work is concerned with the computational complexity of the recognition of $ÞPtwo$, the class of regions of the Euclidian space that can be classified exactly by a two-layered perceptron. Some subclasses of $ÞPtwo$ of particular interest are also studied, such as the class of iterated differences of polyhedra, or the class of regions $V$ that can be classified by a two-layered perceptron with as only hidden units the ones associated to $(d-1)$-dimensional facets of $V$. In this paper, we show that the recognition problem for $ÞPtwo$ as well as most other subclasses considered here is \NPH\ in the most general case. We then identify special cases that admit polynomial time algorithms.},
                         pdf = {https://publications.idiap.ch/attachments/reports/1998/rr98-03.pdf},
                  postscript = {ftp://ftp.idiap.ch/pub/reports/1998/rr98-03.ps.gz},
ipdinar={1998},
ipdmembership={learning},
}



crossreferenced publications: 
@TECHREPORT{Mayo98a,
                      author = {Mayoraz, Eddy},
                    projects = {Idiap},
                       title = {On the Complexity of Recognizing Regions Computable by Two-Layered Perceptrons},
                        type = {Idiap-RR},
                      number = {Idiap-RR-03-1998},
                        year = {1998},
                 institution = {IDIAP},
                    abstract = {This work is concerned with the computational complexity of the recognition of $ÞPtwo$, the class of regions of the Euclidian space that can be classified exactly by a two-layered perceptron. Some subclasses of $ÞPtwo$ of particular interest are also studied, such as the class of iterated differences of polyhedra, or the class of regions $V$ that can be classified by a two-layered perceptron with as only hidden units the ones associated to $(d-1)$-dimensional facets of $V$. In this paper, we show that the recognition problem for $ÞPtwo$ as well as most other subclasses considered here is \NPH\ in the most general case. We then identify special cases that admit polynomial time algorithms.},
                         pdf = {https://publications.idiap.ch/attachments/reports/1998/rr98-03.pdf},
                  postscript = {ftp://ftp.idiap.ch/pub/reports/1998/rr98-03.ps.gz},
ipdmembership={learning},
}