{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:09Z","timestamp":1781077989458,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3450999","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"197-208","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Log-rank and lifting for AND-functions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4311-9071","authenticated-orcid":false,"given":"Alexander","family":"Knop","sequence":"first","affiliation":[{"name":"University of California at San Diego, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shachar","family":"Lovett","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sam","family":"McGuire","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Weiqiang","family":"Yuan","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.020"},{"key":"e_1_3_2_1_2_1","volume-title":"An introduction to finite geometry","author":"Ball S.","year":"2011","unstructured":"\\sc Ball, S., and Weiner, Z. An introduction to finite geometry, 2011. lecture notes, https:\/\/web.mat.upc.edu\/simeon.michael.ball\/IFG.pdf."},{"key":"e_1_3_2_1_3_1","first-page":"130","volume-title":"Proceedings of the 16th Annual IEEE Conference on Computational Complexity","author":"Buhrman H.","year":"2001","unstructured":"\\sc Buhrman, H., and de Wolf, R. Communication complexity lower bounds by polynomials. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001\\\/ (2001), IEEE Computer Society, pp. 120\u2013130."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/120861072"},{"key":"e_1_3_2_1_5_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019","author":"Chattopadhyay A.","year":"2019","unstructured":"\\sc Chattopadhyay, A., Filmus, Y., Koroth, S., Meir, O., and Pitassi, T. Query-to-communication lifting for BPP using inner product. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece\\\/ (2019), C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi, Eds., vol. 132 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp. 35:1\u201335:15."},{"key":"e_1_3_2_1_6_1","volume-title":"Query-to-communication lifting using low-discrepancy gadgets. Electronic Colloquium on Computational Complexity (ECCC) 26\\\/","author":"Chattopadhyay A.","year":"2019","unstructured":"\\sc Chattopadhyay, A., Filmus, Y., Koroth, S., Meir, O., and Pitassi, T. Query-to-communication lifting using low-discrepancy gadgets. Electronic Colloquium on Computational Complexity (ECCC) 26\\\/ (2019), 103."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316353"},{"key":"e_1_3_2_1_8_1","first-page":"2","article-title":"An asymptotically tight bound on the number of relevant variables in a bounded degree boolean function","volume":"40","author":"Chiarelli J.","year":"2020","unstructured":"\\sc Chiarelli, J., Hatami, P., and Saks, M. E. An asymptotically tight bound on the number of relevant variables in a bounded degree boolean function. Comb. 40, 2 (2020), 237\u2013244.","journal-title":"Comb."},{"key":"e_1_3_2_1_9_1","volume-title":"Lifting with simple gadgets and applications to circuit and proof complexity. CoRR abs\/2001.02144\\\/","author":"de Rezende S. F.","year":"2020","unstructured":"\\sc de Rezende, S. F., Meir, O., Nordstr\u00f6m, J., Pitassi, T., Robere, R., and Vinyals, M. Lifting with simple gadgets and applications to circuit and proof complexity. CoRR abs\/2001.02144\\\/ (2020)."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(83)90038-9"},{"key":"e_1_3_2_1_11_1","first-page":"1","article-title":"Query-to-communication lifting for $P^NP$","volume":"28","author":"G\u00f6\u00f6s M.","year":"2019","unstructured":"\\sc G\u00f6\u00f6s, M., Kamath, P., Pitassi, T., and Watson, T. Query-to-communication lifting for $P^NP$. Comput. Complex. 28, 1 (2019), 113\u2013144.","journal-title":"Comput. Complex."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384248"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591838"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.21"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1059369"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0166-6"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1136869"},{"key":"e_1_3_2_1_18_1","volume-title":"The unbounded-error communication complexity of symmetric XOR functions. arXiv preprint arXiv:1704.00777\\\/","author":"Hatami H.","year":"2017","unstructured":"\\sc Hatami, H., and Qian, Y. The unbounded-error communication complexity of symmetric XOR functions. arXiv preprint arXiv:1704.00777\\\/ (2017)."},{"key":"e_1_3_2_1_19_1","volume-title":"Graph generated union-closed families of sets","author":"Knill E.","year":"1994","unstructured":"\\sc Knill, E. Graph generated union-closed families of sets, 1994."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20877-5_39"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21924"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2724704"},{"key":"e_1_3_2_1_23_1","volume-title":"On parity decision trees for fourier-sparse boolean functions. Electronic Colloquium on Computational Complexity (ECCC) 27\\\/","author":"Mande N. S.","year":"2020","unstructured":"\\sc Mande, N. S., and Sanyal, S. On parity decision trees for fourier-sparse boolean functions. Electronic Colloquium on Computational Complexity (ECCC) 27\\\/ (2020), 119."},{"key":"e_1_3_2_1_24_1","volume-title":"On the communication complexity of XOR functions. arXiv preprint arXiv:0909.3392\\\/","author":"Montanaro A.","year":"2009","unstructured":"\\sc Montanaro, A., and Osborne, T. On the communication complexity of XOR functions. arXiv preprint arXiv:0909.3392\\\/ (2009)."},{"key":"e_1_3_2_1_25_1","volume-title":"STACS 2019\\\/","author":"Mukhopadhyay S.","year":"2019","unstructured":"\\sc Mukhopadhyay, S., and Loff, B. Lifting theorems for equality. In STACS 2019\\\/ (2019)."},{"key":"e_1_3_2_1_26_1","volume-title":"On the degree of boolean functions as real polynomials. Computational complexity 4, 4","author":"Nisan N.","year":"1994","unstructured":"\\sc Nisan, N., and Szegedy, M. On the degree of boolean functions as real polynomials. Computational complexity 4, 4 (1994), 301\u2013313."},{"key":"e_1_3_2_1_27_1","volume-title":"47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference)\\\/","volume":"168","author":"Pitassi T.","year":"2020","unstructured":"\\sc Pitassi, T., Shirley, M., and Watson, T. Nondeterministic and randomized boolean hierarchies in communication complexity. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference)\\\/ (2020), A. Czumaj, A. Dawar, and E. Merelli, Eds., vol. 168 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp. 92:1\u201392:19."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050062"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_3_2_1_30_1","volume-title":"42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I\\\/","volume":"9134","author":"Sanyal S.","year":"2015","unstructured":"\\sc Sanyal, S. Near-optimal upper bound on fourier dimension of boolean functions in terms of fourier sparsity. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I\\\/ (2015), M. M. Halld\u00f3rsson, K. Iwama, N. Kobayashi, and B. Speckmann, Eds., vol. 9134 of Lecture Notes in Computer Science, Springer, pp. 1035\u20131045."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC10.5-6-5"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422485"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422485"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.76"},{"key":"e_1_3_2_1_35_1","volume-title":"Parity decision tree complexity and 4-party communication complexity of XOR-functions are polynomially equivalent. arXiv preprint arXiv:1506.02936\\\/","author":"Yao P.","year":"2015","unstructured":"\\sc Yao, P. Parity decision tree complexity and 4-party communication complexity of XOR-functions are polynomially equivalent. arXiv preprint arXiv:1506.02936\\\/ (2015)."},{"key":"e_1_3_2_1_36_1","volume-title":"20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings\\\/","volume":"5878","author":"Zhang S.","year":"2009","unstructured":"\\sc Zhang, S. On the tightness of the buhrman-cleve-wigderson simulation. In Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings\\\/ (2009), Y. Dong, D. Du, and O. H. Ibarra, Eds., vol. 5878 of Lecture Notes in Computer Science, Springer, pp. 434\u2013440."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.136"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC9.3-4-5"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3450999","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3450999","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3450999"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":38,"alternative-id":["10.1145\/3406325.3450999","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3450999","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}