acl acl2013 acl2013-109 acl2013-109-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Malte Nuhn ; Hermann Ney
Abstract: In this paper we show that even for the case of 1:1 substitution ciphers—which encipher plaintext symbols by exchanging them with a unique substitute—finding the optimal decipherment with respect to a bigram language model is NP-hard. We show that in this case the decipherment problem is equivalent to the quadratic assignment problem (QAP). To the best of our knowledge, this connection between the QAP and the decipherment problem has not been known in the literature before.
Friedrich L. Bauer. 2010. Decrypted Secrets: Methods and Maxims of Cryptology. Springer, 4th edition. Martin J. Beckmann and Tjalling C. Koopmans. 1957. Assignment problems and the location of economic activities. Econometrica, 25(4):53–76. Rainer E. Burkard and Eranda ela. 1999. Linear assignment problems and extensions. In Handbook ofCombinatorial Optimization - Supplement Volume A, pages 75–149. Kluwer Academic Publishers. Rainer E. Burkard, Eranda ela, Panos M. Pardalos, and Leonidas S. Pitsoulis. 1998. The quadratic assignment problem. In Handbook of Combinatorial Optimization, pages 241–338. Kluwer Academic Publishers. Eric Corlett and Gerald Penn. 2010. An exact A* method for deciphering letter-substitution ciphers. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1040–1047, Uppsala, Sweden, July. The Association for Computer Linguistics. Qing Dou and Kevin Knight. 2012. Large scale decipherment for out-of-domain machine translation. In Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 266–275, Jeju Island, Korea, July. Association for Computational Linguistics. Kevin Knight and Kenji Yamada. 1999. A computational approach to deciphering unknown scripts. In Proceedings of the ACL Workshop on Unsupervised Learning in Natural Language Processing, number 1, pages 37–44. Association for Computational Linguistics. Kevin Knight, Anish Nair, Nishit Rathod, and Kenji Yamada. 2006. Unsupervised analysis for decipherment problems. In Proceedings of the Conference on Computational Linguistics and Association of Computation Linguistics (COLING/ACL) Main Conference Poster Sessions, pages 499–506, Sydney, Australia, July. Association for Computational Linguistics. Harold W. Kuhn. 1955. The Hungarian method for the assignment problem. Naval Research Logistic Quarterly, 2(1-2):83–97. Malte Nuhn, Arne Mauser, and Hermann Ney. 2012. Deciphering foreign language by combining language models and context vectors. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (ACL), pages 156–164, Jeju, Republic of Korea, July. Association for Computational Linguistics. Sujith Ravi and Kevin Knight. 2008. Attacking decipherment problems optimally with low-order ngram models. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 812–819, Honolulu, Hawaii. Association for Computational Linguistics. Sujith Ravi and Kevin Knight. 2011. Deciphering foreign language. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACLHLT), pages 12–21, Portland, Oregon, USA, June. Association for Computational Linguistics. Sartaj Sahni and Teofilo Gonzalez. 1976. P-complete approximation problems. Journal of the Association for Computing Machinery (JACM), 23(3):555–565, July. 621