{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:49:26Z","timestamp":1760298566380},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2012,12]]},"DOI":"10.1007\/s10623-012-9719-x","type":"journal-article","created":{"date-parts":[[2012,7,23]],"date-time":"2012-07-23T06:56:57Z","timestamp":1343026617000},"page":"383-403","source":"Crossref","is-referenced-by-count":7,"title":["Boolean autoencoders and hypercube clustering complexity"],"prefix":"10.1007","volume":"65","author":[{"given":"P.","family":"Baldi","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,7,24]]},"reference":[{"issue":"1\u20132","key":"9719_CR1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0019-9958(85)80012-7","volume":"66","author":"F. Afrati","year":"1985","unstructured":"Afrati F., Papadimitriou C., Papageorgiou G.: The complexity of cubical graphs. Inf. control 66(1\u20132), 53\u201360 (1985)","journal-title":"Inf. control"},{"key":"9719_CR2","unstructured":"Baldi P.: Autoencoders, unsupervised learning, and deep architectures. In: Journal of Machine Learning Research, Workshop and Conference Proceedings, Proceedings of the 2011 ICML Workshop on Unsupervised and Transfer Learning, vol. 27, Bellevue, WA, pp. 37\u201350 (2012)."},{"key":"9719_CR3","doi-asserted-by":"crossref","unstructured":"Baldi P., Hornik K. (1988) Neural networks and principal component analysis: learning from examples without local minima. Neural Netw. 2(1):53\u201358","DOI":"10.1016\/0893-6080(89)90014-2"},{"key":"9719_CR4","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/j.neunet.2012.04.011","volume":"33","author":"P. Baldi","year":"2012","unstructured":"Baldi P., Lu Z.: Complex-valued autoencoders. Neural Netw. 33, 136\u2013147 (2012)","journal-title":"Neural Netw."},{"key":"9719_CR5","unstructured":"Bengio Y., LeCun Y.: Scaling learning algorithms towards AI. In: Bottou L., Chapelle O., DeCoste D., Weston J. (eds.) Large-scale kernel machines. MIT Press, Cambridge (2007)."},{"issue":"3","key":"9719_CR6","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"E. Berlekamp","year":"1978","unstructured":"Berlekamp E., McEliece R., van Tilborg H.: On the inherent intractability of certain coding problems(Corresp.). IEEE Trans. Inf. Theory 24(3), 384\u2013386 (1978)","journal-title":"Inf. Theory"},{"issue":"1","key":"9719_CR7","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0893-6080(05)80010-3","volume":"5","author":"A. Blum","year":"1992","unstructured":"Blum A., Rivest R.: Training a 3-node neural network is np-complete. Neural Netw. 5(1), 117\u2013127 (1992)","journal-title":"Neural Netw."},{"key":"9719_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","volume":"39","author":"A.P. Dempster","year":"1977","unstructured":"Dempster A.P., Laird N.M., Rubin D.B.: Maximum likelihood from incomplete data via the em algorithm. J. R. Stat. Soc. B 39, 1\u201322 (1977)","journal-title":"J. R. Stat. Soc. B"},{"key":"9719_CR9","volume-title":"Pattern classification","author":"R.O. Duda","year":"2000","unstructured":"Duda R.O., Hart P.E., Stork D.G.: Pattern classification. Wiley, New York (2000)","edition":"2"},{"key":"9719_CR10","first-page":"625","volume":"11","author":"D. Erhan","year":"2010","unstructured":"Erhan D., Bengio Y., Courville A., Manzagol P.A., Vincent P., Bengio S.: Why does unsupervised pre-training help deep learning? J. Mach. Learn. Res. 11, 625\u2013660 (2010)","journal-title":"Mach. Learn. Res."},{"issue":"5814","key":"9719_CR11","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1126\/science.1136800","volume":"315","author":"B. Frey","year":"2007","unstructured":"Frey B., Dueck D.: Clustering by passing messages between data points. Science 315(5814), 972 (2007)","journal-title":"Science"},{"key":"9719_CR12","unstructured":"Garey M., Johnson D.: Computers and intractability. Freeman, San Francisco (1979)."},{"issue":"4","key":"9719_CR13","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0898-1221(88)90212-X","volume":"15","author":"F. Harary","year":"1988","unstructured":"Harary F.: Cubical graphs and cubical dimensions. Comput. Math. Appl. 15(4), 271\u2013275 (1988)","journal-title":"Comput. Math. Appl."},{"issue":"2","key":"9719_CR14","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0012-365X(76)90143-6","volume":"16","author":"J. Hartman","year":"1976","unstructured":"Hartman J.: The homeomorphic embedding of Kn in the m-cube* 1. Discret. Math. 16(2), 157\u2013160 (1976)","journal-title":"Discret. Math."},{"issue":"2","key":"9719_CR15","doi-asserted-by":"crossref","first-page":"338","DOI":"10.21136\/CMJ.1972.101102","volume":"22","author":"I. Havel","year":"1972","unstructured":"Havel I., Mor\u00e1vek J.: B-valuations of graphs. Czechoslov. Math. J. 22(2), 338\u2013351 (1972)","journal-title":"Czechoslov. Math. J."},{"issue":"7","key":"9719_CR16","doi-asserted-by":"crossref","first-page":"1527","DOI":"10.1162\/neco.2006.18.7.1527","volume":"18","author":"G. Hinton","year":"2006","unstructured":"Hinton G., Osindero S., Teh Y.: A fast learning algorithm for deep belief nets. Neural Comput. 18(7), 1527\u20131554 (2006)","journal-title":"Neural Comput."},{"issue":"5786","key":"9719_CR17","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1126\/science.1127647","volume":"313","author":"G. Hinton","year":"2006","unstructured":"Hinton G., Salakhutdinov R.: Reducing the dimensionality of data with neural networks. Science 313(5786), 504 (2006)","journal-title":"Science"},{"key":"9719_CR18","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/0895-7177(88)90486-4","volume":"11","author":"M. Livingston","year":"1988","unstructured":"Livingston M., Stout Q.: Embeddings in hypercubes. Math. Comput. Model. 11, 222\u2013227 (1988)","journal-title":"Math. Comput. Model."},{"key":"9719_CR19","unstructured":"Mahajan M., Nimbhorkar P., Varadarajan K.: The planar k-means problem is NP-hard. In: Proceedings of 3rd Annual Workshop on Algorithms and Computation WALCOM, Kolkata, pp. 274\u2013285 (2009)."},{"key":"9719_CR20","unstructured":"McEliece R.J.: The theory of information and coding. Addison-Wesley Publishing Company, Reading (1977)."},{"issue":"1","key":"9719_CR21","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N. Megiddo","year":"1984","unstructured":"Megiddo N., Supowit K.: On the complexity of some common geometric location problems. SIAM J. Comput. 13(1), 182\u2013196 (1984)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9719_CR22","doi-asserted-by":"crossref","first-page":"794","DOI":"10.1109\/TIT.1981.1056419","volume":"27","author":"S. Ntafos","year":"1981","unstructured":"Ntafos S., Hakimi S.: On the complexity of some coding problems (corresp.). IEEE Trans. Inf. Theory 27(6), 794\u2013796 (1981)","journal-title":"Inf. Theory"},{"key":"9719_CR23","unstructured":"Rumelhart D., Hinton G., Williams R.: Learning internal representations by error propagation. In: Parallel distributed processing, vol 1: Foundations. MIT Press, Cambridge (1986)."},{"key":"9719_CR24","unstructured":"Scholkopf, B., Smola, A.J.: Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT Press, Cambridge (2002)."},{"key":"9719_CR25","first-page":"121","volume":"5","author":"J. Slagle","year":"1975","unstructured":"Slagle J., Chang C., Heller S.: A clustering and data reorganization algorithm. IEEE Trans. Syst. Man Cybern. 5, 121\u2013128 (1975)","journal-title":"IEEE Trans. Syst. Man Cybern."},{"issue":"11","key":"9719_CR26","doi-asserted-by":"crossref","first-page":"2629","DOI":"10.1162\/neco.2008.12-07-661","volume":"20","author":"I. Sutskever","year":"2008","unstructured":"Sutskever I., Hinton G.: Deep, narrow sigmoid belief networks are universal approximators. Neural Comput. 20(11), 2629\u20132636 (2008)","journal-title":"Neural Comput."},{"issue":"6","key":"9719_CR27","doi-asserted-by":"crossref","first-page":"1757","DOI":"10.1109\/18.641542","volume":"43","author":"A. Vardy","year":"1997","unstructured":"Vardy A.: The intractability of computing the minimum distance of a code. IEEE Trans. Inf. Theory 43(6), 1757\u20131766 (1997)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9719_CR28","unstructured":"Vattani A.: A simpler proof of the hardness of k-means clustering in the plane. UCSD Technical Report (2010)."},{"issue":"1","key":"9719_CR29","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BF02579350","volume":"3","author":"P. Winkler","year":"1983","unstructured":"Winkler P.: Proof of the squashed cube conjecture. Combinatorica 3(1), 135\u2013139 (1983)","journal-title":"Combinatorica"}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s10623-012-9719-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,27]],"date-time":"2024-04-27T11:15:34Z","timestamp":1714216534000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10623-012-9719-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,24]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["9719"],"URL":"https:\/\/doi.org\/10.1007\/s10623-012-9719-x","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7,24]]}}}