{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:10:34Z","timestamp":1725567034721},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540280613"},{"type":"electronic","value":"9783540318064"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_1","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T09:34:13Z","timestamp":1127813653000},"page":"1-8","source":"Crossref","is-referenced-by-count":15,"title":["Completeness for Parity Problems"],"prefix":"10.1007","author":[{"given":"Leslie G.","family":"Valiant","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","unstructured":"Arvind, V., Kurur, P.P.: Graph isomorphism is in SPP. Electronic Colloquium on Computational Complexity, Report 37 (2002)"},{"key":"1_CR2","first-page":"203","volume-title":"STOC 1998","author":"R. Beigel","year":"1998","unstructured":"Beigel, R., Buhrman, H., Fortnow, L.: NP might not be as easy as detecting single solutions. In: STOC 1998, pp. 203\u2013208. ACM Press, New York (1998)"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"key":"1_CR4","unstructured":"Cook, M., Bruck, J.: Implementability among predicates. Technical Report. California Institute of Technology, Pasadena, CA (2005)"},{"issue":"2","key":"1_CR5","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF02090768","volume":"23","author":"J.-Y. Cai","year":"1990","unstructured":"Cai, J.-Y., Hemachandra, L.A.: On the power of parity polynomial time. Math. Syst. Theory\u00a023(2), 95\u2013106 (1990)","journal-title":"Math. Syst. Theory"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM J. Computing\u00a05, 704\u2013714 (1976)","journal-title":"SIAM J. Computing"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0304-3975(86)90165-9","volume":"43","author":"L.M. Goldschlager","year":"1986","unstructured":"Goldschlager, L.M., Parberry, I.: On the construction of parallel computers from various bases of Boolean functions. Theoretical Computer Science\u00a043, 43\u201358 (1986)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"1_CR8","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1137\/0219003","volume":"19","author":"H.B. Hunt III","year":"1990","unstructured":"Hunt III, H.B., Stearns, R.E.: The complexity of very simple Boolean formulas with applications. SIAM J. Comput.\u00a019(1), 44\u201370 (1990)","journal-title":"SIAM J. Comput."},{"key":"1_CR9","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0304-3975(03)00080-X","volume":"304","author":"M. Liskiewicz","year":"2003","unstructured":"Liskiewicz, M., Ogihara, M., Toda, S.: The Complexity of Counting Self-avoiding Walks in Subgraphs of Two-dimensional Grids and Hypercubes. Theoretical Computer Science\u00a0304, 129\u2013156 (2003)","journal-title":"Theoretical Computer Science"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Zachos, S.: Two remarks on the power of counting. Theoretical Computer Science, 269\u2013276 (1983)","DOI":"10.1007\/BFb0009651"},{"key":"1_CR11","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1017\/S0370164600044643","volume":"10","author":"P.G. Tait","year":"1880","unstructured":"Tait, P.G.: Remarks on coloring of maps. Proc. Royal Soc. Edinburgh\u00a010, 729 (1880)","journal-title":"Proc. Royal Soc. Edinburgh"},{"issue":"2","key":"1_CR12","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 J. Comput.\u00a021(2), 316\u2013328 (1992)","journal-title":"SIAM J. Comput."},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1112\/jlms\/s1-21.2.98","volume":"21","author":"W.T. Tutte","year":"1946","unstructured":"Tutte, W.T.: On Hamiltonian circuits. J. London Math. Soc.\u00a021, 98\u2013101 (1946)","journal-title":"J. London Math. Soc."},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science\u00a08, 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"1_CR15","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1137\/S0097539700377025","volume":"31","author":"L.G. Valiant","year":"2002","unstructured":"Valiant, L.G.: Quantum circuits that can be simulated classically in polynomial time. SIAM J. on Computing\u00a031(4), 1229\u20131254 (2002)","journal-title":"SIAM J. on Computing"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1109\/FOCS.2004.34","volume-title":"Proc. 45th Annual IEEE Symposium on Foundations of Computer Science","author":"L.G. Valiant","year":"2004","unstructured":"Valiant, L.G.: Holographic algorithms. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, October 17-19, pp. 306\u2013315. IEEE Press, Los Alamitos (2004)"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11523468_1","volume-title":"Automata, Languages and Programming","author":"L.G. Valiant","year":"2005","unstructured":"Valiant, L.G.: Holographic circuits. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1\u201315. Springer, Heidelberg (2005)"},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theoretical Computer Science\u00a047, 85\u201393 (1986)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T18:36:17Z","timestamp":1586457377000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11533719_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}