{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:37:08Z","timestamp":1787341028132,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["CCF-1900460"],"award-info":[{"award-number":["CCF-1900460"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1337\/16"],"award-info":[{"award-number":["1337\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1445\/16"],"award-info":[{"award-number":["1445\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005717","name":"University of Haifa","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005717","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Lifting theorems are theorems that relate the query complexity of a function $f:\\{0,1\\}^{n}\\to \\{0,1\\}$ to the communication complexity of the composed function $f\\circ g^{n}$ for some \u201cgadget\u201d $g:\\{ 0,1\\}^{b}\\times \\{0,1\\}^{b}\\to \\{0,1\\}$. Such theorems allow transferring lower bounds from query complexity to the communication complexity, and have seen numerous applications in recent years. In addition, such theorems can be viewed as a strong generalization of a direct-sum theorem for the gadget $g$. We prove a new lifting theorem that works for all gadgets $g$ that have logarithmic length and exponentially-small discrepancy, for both deterministic and randomized communication complexity. Thus, we significantly increase the range of gadgets for which such lifting theorems hold. Our result has two main motivations: first, allowing a larger variety of gadgets may support more applications. In particular, our work is the first to prove a randomized lifting theorem for logarithmic-size gadgets, thus improving some applications of the theorem. Second, our result can be seen as a strong generalization of a direct-sum theorem for functions with low discrepancy.<\/jats:p>","DOI":"10.1137\/19m1310153","type":"journal-article","created":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T10:09:51Z","timestamp":1613642991000},"page":"171-210","source":"Crossref","is-referenced-by-count":7,"title":["Query-to-Communication Lifting Using Low-Discrepancy Gadgets"],"prefix":"10.1137","volume":"50","author":[{"given":"Arkadev","family":"Chattopadhyay","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1739-0872","authenticated-orcid":true,"given":"Yuval","family":"Filmus","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sajin","family":"Koroth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Or","family":"Meir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,2,18]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"L. Babai, P. Frankl, and J. Simon,\n                      Complexity classes in communication complexity theory (preliminary version)\n                      , in 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, IEEE Computer Society, Los Alamitos, CA, 1986, pp. 337-347.","DOI":"10.1109\/SFCS.1986.15"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"B. Barak, M. Braverman, X. Chen, and A. Rao,\n                      How to compress interactive communication\n                      , in Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, MA, ACM, New York, 2010, pp. 67-76.","DOI":"10.1145\/1806689.1806701"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0220-2"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/17M1139254"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2347282"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"M. Braverman, A. Rao, O. Weinstein, and A. Yehudayoff,\n                      Direct products in communication complexity\n                      , in 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, IEEE Computer Society, Los Alamitos, CA, 2013, pp. 746-755.","DOI":"10.1109\/FOCS.2013.85"},{"key":"atypb7","unstructured":"A. Chattopadhyay, Y. Filmus, S. Koroth, O. Meir, and T. Pitassi,\n                      Query-to-communication lifting for BPP using inner product\n                      , in 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Patras, Greece, C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi, eds., LIPIcs Leibinz Int. Proc. Inform. 132, Schloss Dagstuhl, Wadern, Germany, 2019, 35,https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.35."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-019-00190-7"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"A. Chattopadhyay, M. Kouck\u00fd, B. Loff, and S. Mukhopadhyay,\n                      Simulation beats richness: New data-structure lower bounds\n                      , in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, ACM, New York, 2018, pp. 1013-1020.","DOI":"10.1145\/3188745.3188874"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"S. F. de Rezende, J. Nordstr\u00f6m, and M. Vinyals,\n                      How limited interaction hinders real communication (and what it means for proof and circuit complexity)\n                      , in IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, New Brunswick, NJ, IEEE Computer Society, Los Alamitos, CA, 2016, pp. 295-304.","DOI":"10.1109\/FOCS.2016.40"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0043-7"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8195-x"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792235864"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"A. Ganor, G. Kol, and R. Raz,\n                      Exponential separation of information and communication\n                      , in Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, IEEE Computer Society, Los Alamitos, CA, 2014, pp. 176-185.","DOI":"10.1109\/FOCS.2014.27"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"A. Ganor, G. Kol, and R. Raz,\n                      Exponential separation of communication and external information\n                      , in Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, ACM, New York, 2016, pp. 977-986.","DOI":"10.1145\/2897518.2897535"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/2907939"},{"key":"atypb17","first-page":"902","volume":"2018","author":"Garg A.","year":"2018","journal-title":"STOC"},{"key":"atypb18","unstructured":"M. G\u00f6\u00f6s and T. S. Jayram,\n                      A composition theorem for conical juntas\n                      , in Proceedings of the 31st Conference on Computational Complexity, CCC 2016, Tokyo, 2016, 5,https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2016.5."},{"key":"atypb19","unstructured":"M. G\u00f6\u00f6s, T. S. Jayram, T. Pitassi, and T. Watson,\n                      Randomized communication vs. partition number\n                      , Electronic Colloquium on Computational Complexity (ECCC), TR15-169, 2018."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/15M103145X"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/16M1082007"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"M. G\u00f6\u00f6s, T. Pitassi, and T. Watson,\n                      Deterministic communication vs. partition number\n                      , in Proceedings of IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2015, pp. 1077-1088.","DOI":"10.1109\/FOCS.2015.70"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"M. G\u00f6\u00f6s, T. Pitassi, and T. Watson,\n                      Query-to-communication lifting for BPP\n                      , in Proceedings of IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2017, pp. 132-143.","DOI":"10.1109\/FOCS.2017.21"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/17M1136869"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"R. Jain and H. Klauck,\n                      The partition bound for classical communication complexity and query complexity\n                      , in Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, MA, IEEE, Piscataway, NJ, 2010, pp. 247-258.","DOI":"10.1109\/CCC.2010.31"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"M. Karchmer, R. Raz, and A. Wigderson,\n                      Super-logarithmic depth lower bounds via direct sum in communication complexity\n                      , in Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, IL, IEEE Computer Society, Los Alamitos, CA, 1991, 1991, pp. 299-304.","DOI":"10.1109\/SCT.1991.160273"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/130928273"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"H. Klauck,\n                      A strong direct product theorem for disjointness\n                      , in Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, MA, ACM, New York, 2010, pp. 77-86.","DOI":"10.1145\/1806689.1806702"},{"key":"atypb29","first-page":"4","author":"Kozachinskiy A.","year":"2018","journal-title":"Germany"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan,\n                      Communication Complexity\n                      , Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574948"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"T. Lee, A. Shraibman, and R. Spalek,\n                      A direct product theorem for discrepancy\n                      , in Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, College Park, MD, IEEE, Piscataway, NJ, 2008, pp. 71-80.","DOI":"10.1109\/CCC.2008.25"},{"key":"atypb32","unstructured":"B. Loff and S. Mukhopadhyay,\n                      Lifting theorems for equality\n                      , Electronic Colloquium on Computational Complexity (ECCC), TR18-175, 2019."},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"T. Pitassi and R. Robere,\n                      Strongly exponential lower bounds for monotone computation\n                      , in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, Canada, ACM, New York, 2017, pp. 1246-1255.","DOI":"10.1145\/3055399.3055478"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"T. Pitassi and R. Robere,\n                      Lifting nullstellensatz to monotone span programs over any field\n                      , in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, ACM, New York, 2018, pp. 1207-1219.","DOI":"10.1145\/3188745.3188914"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050062"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"R. Robere, T. Pitassi, B. Rossman, and S. A. Cook,\n                      Exponential lower bounds for monotone span programs\n                      , in IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, New Brunswick, NJ, 2016, IEEE Computer Society, Los Alamitos, CA, pp. 406-415.","DOI":"10.1109\/FOCS.2016.51"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-003-0175-x"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"atypb40","first-page":"444","volume":"9","author":"Shi Y.","year":"2009","journal-title":"Quantum Inf. Comput."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/0204030"},{"key":"atypb42","unstructured":"X. Wu, P. Yao, and H. S. Yuen,\n                      Raz-McKenzie simulation with the inner product gadget\n                      , Electronic Colloquium on Computational Complexity (ECCC), TR17-010, 2017,https:\/\/eccc.weizmann.ac.il\/report\/2017\/010."},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"A. C. Yao,\n                      Lower bounds by probabilistic arguments (extended abstract)\n                      , in 24th Annual Symposium on Foundations of Computer Science, Tucson, AZ, 1983, IEEE Computer Society, Los Alamitos, CA, 1983, pp. 420-428.","DOI":"10.1109\/SFCS.1983.30"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1310153","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:01:48Z","timestamp":1787338908000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1310153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1310153"],"URL":"https:\/\/doi.org\/10.1137\/19m1310153","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}