{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T07:56:26Z","timestamp":1789545386180,"version":"build-2803163510"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2003,1]]},"abstract":"<jats:p>We present a new technique for differentiating deterministic from nondeterministic communication complexity. As a consequence we give almost tight lower bounds for the nondeterministic communication complexity with a restricted number of advice bits. In particular, for any function $t : \\mathbb{N} \\rightarrow \\mathbb{N}$ with $t(n) \\leq n\/2$ we construct a family $(L_{n,t(n)} : n \\in \\mathbb{N})$ of languages such that $L_{n,t(n)} \\subseteq \\{0,1\\}^{2n}$, ${\\rm nc}(L_{n,t(n)}) = O(t(n) \\cdot \\log_2 \\frac{n}{t(n)})$ and ${\\rm nc}(\\overline{L_{n,t(n)}}) = O\\bigl(\\frac{n}{t(n) \\cdot \\log_2 \\frac{n}{t(n)}} + \\log_2 t(n)\\bigr)$, but ${\\rm nc}_{o(t(n))}(L_{n,t(n)}) = \\Omega\\bigl(\\frac{n}{\\log_2 \\frac{n}{t(n)}}\\bigr)$. Here ${\\rm nc}_r(L)$ is the nondeterministic communication complexity of L, assuming that at most r advice bits are utilized. Thus, in contrast to probabilistic communication complexity, a small reduction in the number of advice bits results in almost maximal communication. As a special case we obtain a family $L_n \\subseteq \\{0,1\\}^{2n}$ of languages with {\\rm nc}_{o(\\sqrt{n}\/\\log_2 n)}(L_n) &amp;=&amp; \\Omega\\biggl(\\frac{n}{\\log_2 n}\\biggr),\\\\ {\\rm nc}(L_n) + {\\rm nc}(\\overline{L_n}) &amp;=&amp; O(\\sqrt{n}), and hence nondeterministic communication with slightly restricted access to advice bits is almost quadratically weaker than nondeterminism that always gives correct answers (from the set {yes, no, ?}). As a consequence we obtain an almost optimal separation between Monte-Carlo communication and \"correct\" nondeterminism and answer a question of Beame and Lawry.<\/jats:p>","DOI":"10.1137\/s0097539702414622","type":"journal-article","created":{"date-parts":[[2003,11,17]],"date-time":"2003-11-17T21:00:45Z","timestamp":1069102845000},"page":"43-68","source":"Crossref","is-referenced-by-count":9,"title":["Nondeterministic Communication with a Limited Number of Advice Bits"],"prefix":"10.1137","volume":"33","author":[{"given":"Juraj","family":"Hromkovic","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"H. Abelson,\n                      Lower bound on an information transfer in distributed computation\n                      , in Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, Ann Arbor, MI, 1978, pp. 151\u2013158.","DOI":"10.1109\/SFCS.1978.22"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"A. V. Aho, J. D. Ullman, and M. Yannakakis,\n                      On notions of information transfer in VLSI circuits\n                      , in Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, 1983, pp. 133\u2013139.","DOI":"10.1145\/800061.808742"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"L. Babai, P. Frankl, and J. Simon,\n                      Complexity classes in communication complexity theory\n                      , in Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, Toronto, 1986, pp. 337\u2013347.","DOI":"10.1109\/SFCS.1986.15"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90047-M"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"P. Beame and J. Lawry,\n                      Randomized versus nondeterministisc communication complexity\n                      , in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, Victoria, BC, 1992, pp. 188\u2013199.","DOI":"10.1145\/129712.129732"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200118"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1011"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(81)90009-1"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03442-2"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"J. Hromkovic, G. Schnitger, Nondeterministic communication with a limited number of advice bits, ACM, New York, 1996, 551\u20135601427553","DOI":"10.1145\/237814.238003"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0213052"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"T. S. Jayram, R. Kumar, and D. Sivakumar,\n                      Two applications of information complexity\n                      , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, San Diego, CA, 2003, pp. 673\u2013682.","DOI":"10.1145\/780542.780640"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck, Lower bounds for computation with limited nondeterminism, IEEE Computer Soc., Los Alamitos, CA, 1998, 141\u20131521655689","DOI":"10.1109\/CCC.1998.694600"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Bala Kalyanasundaram, Georg Schnitger, Communication complexity and lower bounds for sequential computation, Teubner\u2010Texte Inform., Vol. 1, Teubner, Stuttgart, 1992, 253\u201326893m:68049","DOI":"10.1007\/978-3-322-95233-2_15"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Thomas Lengauer, VLSI theory, Elsevier, Amsterdam, 1990, 835\u20138681127182","DOI":"10.1016\/B978-0-444-88071-0.50021-7"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn and E. Schmidt,\n                      Las Vegas is better than determinism in VLSI and distributed computing\n                      , in Proceedings of the 14th Annual ACM Symposium on Theory of Computing, San Francisco, 1982, pp. 330\u2013337.","DOI":"10.1145\/800070.802208"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146684"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"M. Yannakakis,\n                      Expressing combinatorial optimization problems by linear programs\n                      , in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, 1988, pp. 223\u2013228.","DOI":"10.1145\/62212.62232"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"A. C. Yao,\n                      Some complexity questions related to distributive computing\n                      , in Proceedings of the 11th Annual ACM Symposium on Theory of Computing, Atlanta, GA, 1979, pp. 209\u2013213.","DOI":"10.1145\/800135.804414"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539702414622","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:20:04Z","timestamp":1787336404000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539702414622"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["10.1137\/S0097539702414622"],"URL":"https:\/\/doi.org\/10.1137\/s0097539702414622","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}