{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:32:14Z","timestamp":1759336334765,"version":"3.40.3"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030677305"},{"type":"electronic","value":"9783030677312"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-67731-2_17","type":"book-chapter","created":{"date-parts":[[2021,1,20]],"date-time":"2021-01-20T10:05:07Z","timestamp":1611137107000},"page":"233-248","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["New Bounds on the Half-Duplex Communication Complexity"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3881-3552","authenticated-orcid":false,"given":"Yuriy","family":"Dementiev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1960-5064","authenticated-orcid":false,"given":"Artur","family":"Ignatiev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7284-9981","authenticated-orcid":false,"given":"Vyacheslav","family":"Sidelnik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8241-5503","authenticated-orcid":false,"given":"Alexander","family":"Smal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7519-0262","authenticated-orcid":false,"given":"Mikhail","family":"Ushakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,1,11]]},"reference":[{"key":"17_CR1","unstructured":"Brodal, G.S., Husfeldt, T.: A communication complexity proof that symmetric functions have logarithmic depth. BRICS (1996). https:\/\/www.brics.dk\/RS\/96\/1\/BRICS-RS-96-1.pdf"},{"issue":"6","key":"17_CR2","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0020-0190(90)90036-W","volume":"35","author":"A Chin","year":"1990","unstructured":"Chin, A.: On the depth complexity of the counting functions. Inf. Process. Lett. 35(6), 325\u2013328 (1990). https:\/\/doi.org\/10.1016\/0020-0190(90)90036-W","journal-title":"Inf. Process. Lett."},{"key":"17_CR3","volume-title":"Elements of Information Theory","author":"TM Cover","year":"2006","unstructured":"Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley-Interscience, New York, USA (2006)"},{"key":"17_CR4","unstructured":"Dementiev, Y., Ignatiev, A., Sidelnik, V., Smal, A., Ushakov, M.: New bounds on the half-duplex communication complexity. Electron. Colloquium Comput. Complex. 27, 117 (2020). https:\/\/eccc.weizmann.ac.il\/report\/2020\/117"},{"key":"17_CR5","unstructured":"Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A.: Half-duplex communication complexity. Electron. Colloquium Comput. Complex. 25, 89 (2018). https:\/\/eccc.weizmann.ac.il\/report\/2018\/089"},{"key":"17_CR6","doi-asserted-by":"publisher","unstructured":"Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A.V.: Half-duplex communication complexity. In: 29th International Symposium on Algorithms and Computation, ISAAC 2018. LIPIcs, vol. 123, pp. 10:1\u201310:12 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.10","DOI":"10.4230\/LIPIcs.ISAAC.2018.10"},{"issue":"3\/4","key":"17_CR7","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01206317","volume":"5","author":"M Karchmer","year":"1995","unstructured":"Karchmer, M., Raz, R., Wigderson, A.: Super-logarithmic depth lower bounds via the direct sum in communication complexity. Comput. Complex. 5(3\/4), 191\u2013204 (1995). https:\/\/doi.org\/10.1007\/BF01206317","journal-title":"Comput. Complex."},{"key":"17_CR8","doi-asserted-by":"publisher","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pp. 539\u2013550 (1988). https:\/\/doi.org\/10.1145\/62212.62265","DOI":"10.1145\/62212.62265"},{"issue":"1","key":"17_CR9","first-page":"21","volume":"9","author":"V Khrapchenko","year":"1971","unstructured":"Khrapchenko, V.: Complexity of the realization of a linear function in the class of II-circuits. Math. Notes Acad. Sci. USSR 9(1), 21\u201323 (1971)","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"17_CR10","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"17_CR11","doi-asserted-by":"publisher","unstructured":"Laplante, S., Lee, T., Szegedy, M.: The quantum adversary method and classical formula size lower bounds. In: 20th Annual IEEE Conference on Computational Complexity (CCC 2005), pp. 76\u201390 (2005). https:\/\/doi.org\/10.1109\/CCC.2005.29","DOI":"10.1109\/CCC.2005.29"},{"key":"17_CR12","unstructured":"Mihajlin, I., Smal, A.: Toward better depth lower bounds: the XOR-KRW conjecture. Electron. Colloquium Comput. Complex. 27, 116 (2020), https:\/\/eccc.weizmann.ac.il\/report\/2020\/116"},{"key":"17_CR13","doi-asserted-by":"publisher","unstructured":"Yao, A.C.C.: Some complexity questions related to distributive computing(preliminary report). In: Proceedings of the 11h Annual ACM Symposium on Theory of Computing, pp. 209\u2013213 (1979). https:\/\/doi.org\/10.1145\/800135.804414","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2021: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-67731-2_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,24]],"date-time":"2021-04-24T15:57:46Z","timestamp":1619279866000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-67731-2_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030677305","9783030677312"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-67731-2_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"11 January 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bolzano-Bozen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 January 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 January 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"47","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem2021.inf.unibz.it\/","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":"100","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":"33","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":"7","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":"33% - 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,1","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":"4,5","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)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}