2026-08-06T04:24:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14304 2024-03-06T10:53:55Z ddc:004 open_access

On Query-To-Communication Lifting for Adversary Bounds Anshu, Anurag Ben-David, Shalev Kundu, Srijita Quantum computing query complexity communication complexity lifting theorems adversary method We 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anurag Anshu and Shalev Ben-David and Srijita Kundu 2021 Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2021.30 urn:nbn:de:0030-drops-143042 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.30 eng https://creativecommons.org/licenses/by/4.0/legalcode