Anshu, AnuragShalev, Ben-DavidSrijita, Kundu2024-04-172020-12-07Anurag Anshu, Shalev Ben-David, and Srijita Kundu. 2021. On query-to-communication lifting for adversary bounds. In Proceedings of the 36th Computational Complexity Conference (CCC '21). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, DEU, Article lipics, 1. https://doi.org/10.4230/LIPIcs.CCC.2021.30https://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37378336We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1. We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2. Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3. Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.en-USConference Paper2024-04-1710.4230/LIPIcs.CCC.2021.30