2026-08-21T17:56:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27460 2026-08-21T14:42:40Z ddc:004 open_access

Randomized and Quantum Lifting for One-Way Conservative NOF Model Wang, Haoyu Wu, Pei communication complexity lifting theorem number-on-forehead model We consider lifting theorems that transfer lower bounds for two-party communication problems to multiparty communication problems. In particular, following the deterministic Number-on-Forehead (NOF) lifting framework of Yang and Zhang, we study randomized and quantum one-way NOF lifting for composed problems F(z,𝐱) = f(z,G(𝐱)). We work in a one-way NOF model in which only the last player’s view is restricted. The other players have their usual NOF views and communicate as usual, but the last player sees only the gadget output G(𝐱), not the gadget input 𝐱. This kind of restricted-view has appeared in the NOF literature under the name conservative model. Our main contribution is a pair of lifting theorems for this model. In the randomized setting, we show that lifting follows when each preimage G^{-1}(v), the set of gadget inputs with output v, looks pseudorandom to large cylinder intersections. In the quantum setting, we prove an analogous theorem. Equivalently, conservative protocols for F(z,𝐱) = f(z,G(𝐱)) can be converted into two-party one-way protocols for f(z,v) with comparable cost, and the error loss controlled by the corresponding pseudorandomness parameters. Thus, this restriction isolates a setting in which both randomized and quantum one-way NOF lifting can be proved by a direct simulation argument. We prove the required pseudorandomness properties for the generalized inner product gadget over finite fields, using the multiparty character-sum bounds of Yang and Zhang, and for random gadgets, which give non-explicit lifting. As applications, Boolean Hidden Matching yields a randomized-versus-quantum separation in the conservative NOF model, and lifting INDEX gives randomized and quantum conservative NOF lower bounds for O(log n) players. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haoyu Wang and Pei Wu 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.78 urn:nbn:de:0030-drops-274604 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.78 eng https://creativecommons.org/licenses/by/4.0/legalcode