{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T15:52:40Z","timestamp":1782489160255,"version":"3.54.5"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030199548","type":"print"},{"value":"9783030199555","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-19955-5_20","type":"book-chapter","created":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T23:10:01Z","timestamp":1561331401000},"page":"228-236","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["On the Quantum and Classical Complexity of Solving Subtraction Games"],"prefix":"10.1007","author":[{"given":"Dmitry","family":"Kravchenko","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kamil","family":"Khadiev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Danil","family":"Serov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,5,16]]},"reference":[{"key":"20_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-319-98355-4_9","volume-title":"Adventures Between Lower Bounds and Higher Altitudes","author":"F Ablayev","year":"2018","unstructured":"Ablayev, F., Ablayev, M., Khadiev, K., Vasiliev, A.: Classical and quantum computations with restricted memory. In: B\u00f6ckenhauer, H.-J., Komm, D., Unger, W. (eds.) Adventures Between Lower Bounds and Higher Altitudes. LNCS, vol. 11011, pp. 129\u2013155. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-98355-4_9"},{"key":"20_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-319-73117-9_14","volume-title":"SOFSEM 2018: Theory and Practice of Computer Science","author":"F Ablayev","year":"2018","unstructured":"Ablayev, F., Ambainis, A., Khadiev, K., Khadieva, A.: Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test. In: Tjoa, A.M., Bellatreche, L., Biffl, S., van Leeuwen, J., Wiedermann, J. (eds.) SOFSEM 2018. LNCS, vol. 10706, pp. 197\u2013211. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-73117-9_14"},{"issue":"6","key":"20_CR3","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1134\/S199508021606007X","volume":"37","author":"F Ablayev","year":"2016","unstructured":"Ablayev, F., Gainutdinova, A., Khadiev, K., Yakary\u0131lmaz, A.: Very narrow quantum OBDDs and width hierarchies for classical OBDDs. Lobachevskii J. Math. 37(6), 670\u2013682 (2016)","journal-title":"Lobachevskii J. Math."},{"key":"20_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-319-09704-6_6","volume-title":"Descriptional Complexity of Formal Systems","author":"F Ablayev","year":"2014","unstructured":"Ablayev, F., Gainutdinova, A., Khadiev, K., Yakary\u0131lmaz, A.: Very narrow quantum OBDDs and width hierarchies for classical OBDDs. In: J\u00fcrgensen, H., Karhum\u00e4ki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 53\u201364. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-09704-6_6"},{"key":"20_CR5","unstructured":"Ambainis, A.: Understanding quantum algorithms via query complexity. arXiv preprint arXiv:1712.06349 (2017)"},{"issue":"3","key":"20_CR6","doi-asserted-by":"publisher","first-page":"030301","DOI":"10.1103\/PhysRevA.64.030301","volume":"64","author":"SC Benjamin","year":"2001","unstructured":"Benjamin, S.C., Hayden, P.M.: Multiplayer quantum games. Phys. Rev. A 64(3), 030301 (2001)","journal-title":"Phys. Rev. A"},{"issue":"4\u20135","key":"20_CR7","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M Boyer","year":"1998","unstructured":"Boyer, M., Brassard, G., H\u00f8yer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik 46(4\u20135), 493\u2013505 (1998)","journal-title":"Fortschritte der Physik"},{"key":"20_CR8","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. McGraw-Hill, New York (2001)","edition":"2"},{"key":"20_CR9","unstructured":"De Wolf, R.: Quantum computing and communication complexity. Ph.D. thesis (2001)"},{"issue":"14\u201315","key":"20_CR10","doi-asserted-by":"publisher","first-page":"2543","DOI":"10.1080\/09500340008232180","volume":"47","author":"J Eisert","year":"2000","unstructured":"Eisert, J., Wilkens, M.: Quantum games. J. Mod. Opt. 47(14\u201315), 2543\u20132556 (2000)","journal-title":"J. Mod. Opt."},{"issue":"15","key":"20_CR11","doi-asserted-by":"publisher","first-page":"3077","DOI":"10.1103\/PhysRevLett.83.3077","volume":"83","author":"J Eisert","year":"1999","unstructured":"Eisert, J., Wilkens, M., Lewenstein, M.: Quantum games and quantum strategies. Phys. Rev. Lett. 83(15), 3077 (1999)","journal-title":"Phys. Rev. Lett."},{"key":"20_CR12","unstructured":"Ferguson, T.S.: Game theory class notes for math 167, fall 2000 (2000). https:\/\/www.cs.cmu.edu\/afs\/cs\/academic\/class\/15859-f01\/www\/notes\/comb.pdf"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212\u2013219. ACM (1996)","DOI":"10.1145\/237814.237866"},{"key":"20_CR14","first-page":"6","volume":"2","author":"PM Grundy","year":"1939","unstructured":"Grundy, P.M.: Mathematics and games. Eureka 2, 6\u20138 (1939)","journal-title":"Eureka"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-319-94631-3_15","volume-title":"Descriptional Complexity of Formal Systems","author":"R Ibrahimov","year":"2018","unstructured":"Ibrahimov, R., Khadiev, K., Pr\u016bsis, K., Yakary\u0131lmaz, A.: Error-free affine, unitary, and probabilistic OBDDs. In: Konstantinidis, S., Pighizzini, G. (eds.) DCFS 2018. LNCS, vol. 10952, pp. 175\u2013187. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-94631-3_15"},{"key":"20_CR16","unstructured":"Jordan, S.: Bounded error quantum algorithms zoo. https:\/\/math.nist.gov\/quantum\/zoo"},{"key":"20_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-319-58747-9_16","volume-title":"Computer Science \u2013 Theory and Applications","author":"K Khadiev","year":"2017","unstructured":"Khadiev, K., Khadieva, A.: Reordering method and hierarchies for quantum and classical ordered binary decision diagrams. In: Weil, P. (ed.) CSR 2017. LNCS, vol. 10304, pp. 162\u2013175. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-58747-9_16"},{"issue":"9","key":"20_CR18","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1134\/S1995080218090421","volume":"39","author":"K Khadiev","year":"2018","unstructured":"Khadiev, K., Khadieva, A., Mannapov, I.: Quantum online algorithms with respect to space and advice complexity. Lobachevskii J. Math. 39(9), 1210\u20131220 (2018)","journal-title":"Lobachevskii J. Math."},{"key":"20_CR19","doi-asserted-by":"publisher","unstructured":"Khadiev, K., Safina, L.: Quantum algorithm for dynamic programming approach for dags. Applications for zhegalkin polynomial evaluation and some problems on dags. In: Proceedings of Unconventional Computation and Natural Computation 2019. LNCS, vol. 11493 (2019). https:\/\/doi.org\/10.1007\/978-3-030-19311-9_13","DOI":"10.1007\/978-3-030-19311-9_13"},{"key":"20_CR20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667","volume-title":"Quantum Computation and Quantum Information","author":"MA Nielsen","year":"2010","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, New York (2010)"},{"key":"20_CR21","first-page":"438","volume":"41","author":"RP Sprague","year":"1935","unstructured":"Sprague, R.P.: \u00dcber mathematische kampfspiele. Tohoku Math. J. 41, 438\u2013444 (1935)","journal-title":"Tohoku Math. J."}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-19955-5_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T17:02:41Z","timestamp":1710349361000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-19955-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030199548","9783030199555"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-19955-5_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"16 May 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Novosibirsk","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"71","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"44% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.27","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}