{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T03:49:45Z","timestamp":1761709785527},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,10,29]],"date-time":"2020-10-29T00:00:00Z","timestamp":1603929600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,10,29]],"date-time":"2020-10-29T00:00:00Z","timestamp":1603929600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00037-020-00197-5","type":"journal-article","created":{"date-parts":[[2020,10,29]],"date-time":"2020-10-29T20:02:40Z","timestamp":1604001760000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Robustness of LWPP and WPP, with an Application to Graph Reconstruction"],"prefix":"10.1007","volume":"29","author":[{"given":"Edith","family":"Hemaspaandra","sequence":"first","affiliation":[]},{"given":"Lane A.","family":"Hemaspaandra","sequence":"additional","affiliation":[]},{"given":"Holger","family":"Spakowski","sequence":"additional","affiliation":[]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,10,29]]},"reference":[{"key":"197_CR1","doi-asserted-by":"crossref","unstructured":"L. Babai (2016). Graph Isomorphism in Quasipolynomial Time. In Proceedings of the 48th ACM Symposium on Theory of Computing, 684\u2013697. ACM Press","DOI":"10.1145\/2897518.2897542"},{"key":"197_CR2","doi-asserted-by":"crossref","unstructured":"R. Beigel (1989). On the Relativized Power of Additional Accepting Paths. In Proceedings of the 4th Structure in Complexity Theory Conference, 216\u2013224. IEEE Computer Society Press","DOI":"10.1109\/SCT.1989.41827"},{"key":"197_CR3","doi-asserted-by":"crossref","unstructured":"R. Beigel (1997). Closure Properties of GapP and #P. In Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems, 144\u2013146. IEEE Computer Society Press","DOI":"10.1109\/ISTCS.1997.595166"},{"issue":"3","key":"197_CR4","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1006\/jcss.1997.1497","volume":"55","author":"J Berstel","year":"1997","unstructured":"Berstel, J., Boasson, L.: The Set of Minimal Words of a Context-Free Language is Context-Free. Journal of Computer and System Sciences 55(3), 477\u2013488 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"197_CR5","unstructured":"A. Berthiaume & G. Brassard (1992). The Quantum Challenge to Structural Complexity Theory. In Proceedings of the 7th Structure in Complexity Theory Conference, 132\u2013137. IEEE Computer Society Press"},{"issue":"12","key":"197_CR6","doi-asserted-by":"publisher","first-page":"2521","DOI":"10.1080\/09500349414552351","volume":"41","author":"A Berthiaume","year":"1994","unstructured":"Berthiaume, A., Brassard, G.: Oracle Quantum Computing. Journal of Modern Optics 41(12), 2521\u20132535 (1994)","journal-title":"Journal of Modern Optics"},{"issue":"2","key":"197_CR7","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0304-3975(93)90160-U","volume":"119","author":"J-C Birget","year":"1993","unstructured":"Birget, J.-C.: Partial Orders on Words, Minimal Elements of Regular Languages and State Complexity. Theoretical Computer Science 119(2), 267\u2013291 (1993)","journal-title":"Theoretical Computer Science"},{"key":"197_CR8","doi-asserted-by":"crossref","unstructured":"J. Bondy (1991). A Graph Reconstructor\u2019s Manual. In Surveys in Combinatorics, London Mathematical Society Lecture Notes Series 66, 221\u2013252. Cambridge University Press","DOI":"10.1017\/CBO9780511666216.009"},{"issue":"3","key":"197_CR9","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1002\/jgt.3190010306","volume":"1","author":"J Bondy","year":"1977","unstructured":"Bondy, J., Hemminger, R.: Graph Reconstruction-A Survey. Journal of Graph Theory 1(3), 227\u2013268 (1977)","journal-title":"Journal of Graph Theory"},{"issue":"2","key":"197_CR10","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(92)90125-Y","volume":"104","author":"D Bovet","year":"1992","unstructured":"Bovet, D., Crescenzi, P., Silvestri, R.: A Uniform Approach to Define Complexity Classes. Theoretical Computer Science 104(2), 263\u2013283 (1992)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"197_CR11","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1137\/0218007","volume":"18","author":"J Cai","year":"1989","unstructured":"Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The Boolean Hierarchy II: Applications. SIAM Journal on Computing 18(1), 95\u2013111 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"197_CR12","unstructured":"J. Cox & T. Pay (2018). An Overview of Some Semantic and Syntactic Complexity Classes. Technical Report arXiv:1806.03501 [cs.CC], Computing Research Repository, arXiv.org\/corr\/."},{"key":"197_CR133","doi-asserted-by":"crossref","unstructured":"The Editors (of the Journal of Graph Theory) (1977). Editorial Note. Journal of Graph Theory 1(3), 191","DOI":"10.1002\/jgt.3190010302"},{"issue":"2","key":"197_CR13","first-page":"199","volume":"36","author":"S Fenner","year":"2003","unstructured":"Fenner, S.: PP-Lowness and a Simple Definition of AWPP. ACM Transactions on Computer Systems 36(2), 199\u2013212 (2003)","journal-title":"ACM Transactions on Computer Systems"},{"issue":"1","key":"197_CR14","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"S Fenner","year":"1994","unstructured":"Fenner, S., Fortnow, L., Kurtz, S.: Gap-Definable Counting Classes. Journal of Computer and System Sciences 48(1), 116\u2013148 (1994)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"197_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0890-5401(03)00018-X","volume":"182","author":"S Fenner","year":"2003","unstructured":"Fenner, S., Fortnow, L., Kurtz, S., Li, L.: An Oracle Builder's Toolkit. Information and Computation 182(2), 95\u2013136 (2003)","journal-title":"Information and Computation"},{"issue":"2","key":"197_CR16","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1006\/jcss.1999.1651","volume":"59","author":"Fortnow & Rogers","year":"1999","unstructured":"Fortnow & Rogers: Complexity Limitations on Quantum Computation. Journal of Computer and System Sciences 59(2), 240\u2013252 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"197_CR17","first-page":"229","volume":"52","author":"L Fortnow","year":"1994","unstructured":"Fortnow, L.: The Role of Relativization in Complexity Theory. Bulletin of the European Association for Theoretical Computer Science 52, 229\u2013244 (1994)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"197_CR18","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M Furst","year":"1984","unstructured":"Furst, M., Saxe, J., Sipser, M.: Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory 17, 13\u201327 (1984)","journal-title":"Mathematical Systems Theory"},{"key":"197_CR19","unstructured":"M. de Graaf & P. Valiant (2002). Comparing EQP and $${\\rm MOD}_{p}^{k}$$P using polynomial degree lower bounds. Technical Report arXiv:quantph\/0211179, arXiv.org"},{"issue":"2","key":"197_CR20","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J Grollmann","year":"1988","unstructured":"Grollmann, J., Selman, A.: Complexity Measures for Public- Key Cryptosystems. SIAM Journal on Computing 17(2), 309\u2013335 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"197_CR21","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1137\/S0097539792240467","volume":"26","author":"Y Han","year":"1997","unstructured":"Han, Y., Hemaspaandra, L., Thierauf, T.: Threshold Computation and Cryptographic Security. SIAM Journal on Computing 26(1), 59\u201378 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"197_CR22","first-page":"144","volume":"47","author":"J Hartmanis","year":"1992","unstructured":"Hartmanis, J., Chang, R., Chari, S., Ranjan, D., Rohatgi, P.: Relativization: A Revisionistic Retrospective. Bulletin of the European Association for Theoretical Computer Science 47, 144\u2013153 (1992)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"197_CR23","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, R. Chang, D. Ranjan & P. Rohatgi (1990). Structural Complexity Theory: Recent Surprises. In Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory, 1\u201312. Springer-Verlag Lecture Notes in Computer Science #447","DOI":"10.1007\/3-540-52846-6_73"},{"key":"197_CR24","unstructured":"J. H\u00e5stad (1987). Computational Limitations of Small-Depth Circuits. MIT Press"},{"issue":"2","key":"197_CR25","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.dam.2006.04.038","volume":"155","author":"E Hemaspaandra","year":"2007","unstructured":"Hemaspaandra, E., Hemaspaandra, L., Radziszowski, S., Tripathi, R.: Complexity Results in Graph Reconstruction. Discrete Applied Mathematics 155(2), 103\u2013118 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"197_CR26","unstructured":"E. Hemaspaandra, L. Hemaspaandra, H. Spakowski & O. Watanabe (2018). The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, volume 117, 51:1\u201351:14. Leibniz International Proceedings in Informatics (LIPIcs)"},{"key":"197_CR27","unstructured":"L. Hemaspaandra, R. Kr\u00e1lovi\u010d, R. Kr\u00e1lovi\u010d & B. Ravikumar. The Complexity of Culling: Decimation, Minimal Words, and Many-One Reductions. In preparation"},{"key":"197_CR28","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, L., Ogihara, M.: The Complexity Theory Companion. Springer (2002)","DOI":"10.1007\/978-3-662-04880-1"},{"key":"197_CR29","unstructured":"L. Hemaspaandra & M. Zimand (1993). Strong Forms of Balanced Immunity. Technical Report TR-480, Department of Computer Science, University of Rochester, Rochester, NY. Revised, May 1994"},{"key":"197_CR30","unstructured":"P. Kelly (1942). On Isometric Transformations. Ph.D. thesis, University of Wisconsin, USA"},{"issue":"1","key":"197_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(85)90085-4","volume":"37","author":"K Ko","year":"1985","unstructured":"Ko, K.: On Some Natural Complete Operators. Theoretical Computer Science 37(1), 1\u201330 (1985)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"197_CR32","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1137\/0218027","volume":"18","author":"K Ko","year":"1989","unstructured":"Ko, K.: Relativized Polynomial-Time Hierarchies Having Exactly k Levels. SIAM Journal on Computing 18(2), 392\u2013408 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"197_CR33","doi-asserted-by":"crossref","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning & J. Tor\u00e1n (1992). Graph Isomorphism is low for PP. Computational Complexity 2, 301-330.","DOI":"10.1007\/BF01200427"},{"key":"197_CR34","unstructured":"D. Kratsch & L. Hemachandra (1991). On the Complexity of Graph Reconstruction. In Proceedings of the 8th Conference on Fundamentals of Computation Theory, 318\u2013328. Springer-Verlag Lecture Notes in Computer Science #529"},{"issue":"3","key":"197_CR35","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/BF01578845","volume":"27","author":"D Kratsch","year":"1994","unstructured":"Kratsch, D., Hemaspaandra, L.: On the Complexity of Graph Reconstruction. Mathematical Systems Theory 27(3), 257\u2013273 (1994)","journal-title":"Mathematical Systems Theory"},{"key":"197_CR36","unstructured":"Lauri, J., Scapellato, R.: Topics in Graph Automorphisms and Reconstruction. Cambridge University Press (2003)"},{"key":"197_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(82)90085-8","volume":"21","author":"T Long","year":"1982","unstructured":"Long, T.: Strong Nondeterministic Polynomial-Time Reducibilities. Theoretical Computer Science 21, 1\u201325 (1982)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"197_CR38","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1093\/qmath\/33.3.345","volume":"33","author":"A Mansfield","year":"1982","unstructured":"Mansfield, A.: The Relationship between the Computational Complexities of the Legitimate Deck and Isomorphism Problems. Quart. J. Math. Ser. 33(2), 345\u2013347 (1982)","journal-title":"Quart. J. Math. Ser."},{"key":"197_CR39","first-page":"177","volume":"63","author":"B Manvel","year":"1988","unstructured":"Manvel, B.: Reconstruction of Graphs: Progress and Prospects. Congressus Numerantium 63, 177\u2013187 (1988)","journal-title":"Congressus Numerantium"},{"key":"197_CR40","unstructured":"C. St. J. A. Nash-Williams (1978). The Reconstruction Problem. In Selected Topics in Graph Theory, L. Beineke & R. Wilson, editors, 205\u2013236. Academic Press"},{"issue":"3","key":"197_CR41","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(93)90006-I","volume":"46","author":"M Ogiwara","year":"1993","unstructured":"Ogiwara, M., Hemachandra, L.: A Complexity Theory for Feasible Closure Properties. Journal of Computer and System Sciences 46(3), 295\u2013325 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"197_CR42","doi-asserted-by":"crossref","unstructured":"R. Rao, J. Rothe & O. Watanabe (1994). Upward Separation for FewP and Related Classes. Information Processing Letters 52(4), 175\u2013180. Corrigendum in Information Processing Letters, 74(1\u20132), 89","DOI":"10.1016\/0020-0190(94)90123-6"},{"key":"197_CR43","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1215\/ijm\/1255631807","volume":"6","author":"J Rosser","year":"1962","unstructured":"Rosser, J., Schoenfeld, L.: Approximate Formulas for Some Functions of Prime Numbers. Illinois Journal of Mathematics 6, 64\u201394 (1962)","journal-title":"Illinois Journal of Mathematics"},{"issue":"2","key":"197_CR44","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1051\/ita:1999100","volume":"33","author":"J Rothe","year":"1999","unstructured":"Rothe, J.: Immunity and Simplicity for Exact Counting and Other Counting Classes. RAIRO Theoretical Informatics and Applications 33(2), 159\u2013176 (1999)","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"197_CR45","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning (1983). A Low and a High Hierarchy within NP. Journal of Computer and System Sciences 27, 14-28.","DOI":"10.1016\/0022-0000(83)90027-2"},{"key":"197_CR46","unstructured":"J. Simon (1975). On Some Central Problems in Computational Complexity. Ph.D. thesis, Cornell University, Ithaca, N.Y. Available as Cornell Department of Computer Science Technical Report TR75-224"},{"issue":"1","key":"197_CR47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2004.10.009","volume":"200","author":"H Spakowski","year":"2005","unstructured":"Spakowski, H., Thakur, M., Tripathi, R.: Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties. Information and Computation 200(1), 1\u201334 (2005)","journal-title":"Information and Computation"},{"issue":"4","key":"197_CR48","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1016\/j.jcss.2006.01.002","volume":"72","author":"H Spakowski","year":"2006","unstructured":"Spakowski, H., Tripathi, R.: LWPP and WPP Are Not Uniformly Gap-Definable. Journal of Computer and System Sciences 72(4), 660\u2013689 (2006)","journal-title":"Journal of Computer and System Sciences"},{"key":"197_CR49","unstructured":"L. Stockmeyer & A. Meyer (1973). Word Problems Requiring Exponential Time. In Proceedings of the 5th ACM Symposium on Theory of Computing, 1\u20139. ACM Press"},{"key":"197_CR50","doi-asserted-by":"crossref","unstructured":"J. Tarui (1991). Degree Complexity of Boolean Functions and Its Applications to Relativized Separations. In Proceedings of the 6th Annual Conference on Structure in Complexity Theory, 382\u2013390. IEEE Computer Society Press","DOI":"10.1109\/SCT.1991.160282"},{"issue":"2","key":"197_CR51","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1137\/0221023","volume":"21","author":"S Toda","year":"1992","unstructured":"Toda, S., Ogiwara, M.: Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing 21(2), 316\u2013328 (1992)","journal-title":"SIAM Journal on Computing"},{"key":"197_CR52","volume-title":"A Collection of Mathematical Problems","author":"S Ulam","year":"1960","unstructured":"Ulam, S.: A Collection of Mathematical Problems. Interscience Publishers, New York (1960)"},{"issue":"1","key":"197_CR53","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L Valiant","year":"1976","unstructured":"Valiant, L.: The Relative Complexity of Checking and Evaluating. Information Processing Letters 5(1), 20\u201323 (1976)","journal-title":"Information Processing Letters"},{"issue":"2","key":"197_CR54","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L Valiant","year":"1979","unstructured":"Valiant, L.: The Complexity of Computing the Permanent. Theoretical Computer Science 8(2), 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"197_CR55","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1137\/S0097539703420651","volume":"33","author":"N Vinodchandran","year":"2004","unstructured":"Vinodchandran, N.: Counting Complexity of Solvable Black-Box Group Problems. SIAM Journal on Computing 33(4), 852\u2013869 (2004)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"197_CR56","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K Wagner","year":"1986","unstructured":"Wagner, K.: The Complexity of Combinatorial Problems with Succinct Input Representations. Acta Informatica 23(3), 325\u2013356 (1986)","journal-title":"Acta Informatica"},{"issue":"3","key":"197_CR57","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0020-0190(88)90071-3","volume":"27","author":"O Watanabe","year":"1988","unstructured":"Watanabe, O.: On Hardness of One-Way Functions. Information Processing Letters 27(3), 151\u2013157 (1988)","journal-title":"Information Processing Letters"},{"key":"197_CR58","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C Wrathall","year":"1977","unstructured":"Wrathall, C.: Complete Sets and the Polynomial-time Hierarchy. Theoretical Computer Science 3, 23\u201333 (1977)","journal-title":"Theoretical Computer Science"},{"key":"197_CR59","doi-asserted-by":"crossref","unstructured":"A. Yao (1985). Separating the Polynomial-Time Hierarchy by Oracles. In Proceedings of the 26th IEEE Symposium on Foundations of Computer Science, 1\u201310","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-020-00197-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-020-00197-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-020-00197-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,11]],"date-time":"2021-04-11T09:31:23Z","timestamp":1618133483000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-020-00197-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,29]]},"references-count":60,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["197"],"URL":"https:\/\/doi.org\/10.1007\/s00037-020-00197-5","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,29]]},"assertion":[{"value":"11 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"7"}}