%Aigaion2 BibTeX export from Idiap Publications
%Friday 05 December 2025 01:08:24 PM

@INPROCEEDINGS{Mayo97a1,
                      author = {Mayoraz, Eddy},
                      editor = {Gerstner, W. and Germond, A. and Hasler, M. and Nicoud, J. -D.},
                    projects = {Idiap},
                       title = {On the Complexity of Recognizing Iterated Differences of Polyhedra},
                   booktitle = {Proceedings of the International Conference on Artificial Neural Networks (ICANN'97)},
                      series = {Lecture Notes in Computer Science},
                      number = {1327},
                        year = {1997},
                   publisher = {Springer-Verlag},
                        note = {IDIAP-RR 97-10},
                    crossref = {mayo97a},
                    abstract = {The iterated difference of polyhedra $V = P_1 \backslash ( P_2 \backslash (... P_k ) ... )$ has been proposed independently in [Zwie-Aart-Wess92] and [Shon93] as a sufficient condition for $V$ to be exactly computable by a two-layered neural network. An algorithm checking whether $V$ included in $R^d$ is an iterated difference of polyhedra is proposed in [Zwie-Aart-Wess92]. However, this algorithm is not practically usable because it has a high computational complexity and it was only conjectured to stop with a negative answer when applied to a region which is not an iterated difference of polyhedra. This paper sheds some light on the nature of iterated difference of polyhedra. The outcomes are\,: (i) an algorithm which always stops after a small number of iterations, (ii) sufficient conditions for this algorithm to be polynomial and (iii) the proof that an iterated difference of polyhedra can be exactly computed by a two-layered neural network using only essential hyperplanes.},
                         pdf = {https://publications.idiap.ch/attachments/reports/1997/rr97-10.pdf},
                  postscript = {ftp://ftp.idiap.ch/pub/reports/1997/rr97-10.ps.gz},
ipdmembership={learning},
}



crossreferenced publications: 
@TECHREPORT{Mayo97a,
                      author = {Mayoraz, Eddy},
                    projects = {Idiap},
                       title = {On the Complexity of Recognizing Iterated Differences of Polyhedra},
                        type = {Idiap-RR},
                      number = {Idiap-RR-10-1997},
                        year = {1997},
                 institution = {IDIAP},
                        note = {Published in the Proceedings of ICANN'97},
                    abstract = {The iterated difference of polyhedra $V = P_1 \backslash ( P_2 \backslash (... P_k ) ... )$ has been proposed independently in [Zwie-Aart-Wess92] and [Shon93] as a sufficient condition for $V$ to be exactly computable by a two-layered neural network. An algorithm checking whether $V$ included in $R^d$ is an iterated difference of polyhedra is proposed in [Zwie-Aart-Wess92]. However, this algorithm is not practically usable because it has a high computational complexity and it was only conjectured to stop with a negative answer when applied to a region which is not an iterated difference of polyhedra. This paper sheds some light on the nature of iterated difference of polyhedra. The outcomes are\,: (i) an algorithm which always stops after a small number of iterations, (ii) sufficient conditions for this algorithm to be polynomial and (iii) the proof that an iterated difference of polyhedra can be exactly computed by a two-layered neural network using only essential hyperplanes.},
                         pdf = {https://publications.idiap.ch/attachments/reports/1997/rr97-10.pdf},
                  postscript = {ftp://ftp.idiap.ch/pub/reports/1997/rr97-10.ps.gz},
ipdmembership={learning},
}