Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.35
URN: urn:nbn:de:0030-drops-106110
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10611/
Chattopadhyay, Arkadev ; Filmus, Yuval ; Koroth, Sajin ; Meir, Or ; Pitassi, Toniann
Query-To-Communication Lifting for BPP Using Inner Product
| pdf-format: |
|
Abstract
We prove a new query-to-communication lifting for randomized protocols, with inner product as gadget. This allows us to use a much smaller gadget, leading to a more efficient lifting. Prior to this work, such a theorem was known only for deterministic protocols, due to Chattopadhyay et al. [Arkadev Chattopadhyay et al., 2017] and Wu et al. [Xiaodi Wu et al., 2017]. The only query-to-communication lifting result for randomized protocols, due to Göös, Pitassi and Watson [Mika Göös et al., 2017], used the much larger indexing gadget.Our proof also provides a unified treatment of randomized and deterministic lifting. Most existing proofs of deterministic lifting theorems use a measure of information known as thickness. In contrast, Göös, Pitassi and Watson [Mika Göös et al., 2017] used blockwise min-entropy as a measure of information. Our proof uses the blockwise min-entropy framework to prove lifting theorems in both settings in a unified way.
BibTeX - Entry
@InProceedings{chattopadhyay_et_al:LIPIcs:2019:10611,
author = {Arkadev Chattopadhyay and Yuval Filmus and Sajin Koroth and Or Meir and Toniann Pitassi},
title = {{Query-To-Communication Lifting for BPP Using Inner Product}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {35:1--35:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-109-2},
ISSN = {1868-8969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10611},
URN = {urn:nbn:de:0030-drops-106110},
doi = {10.4230/LIPIcs.ICALP.2019.35},
annote = {Keywords: lifting theorems, inner product, BPP Lifting, Deterministic Lifting}
}
| Keywords: | lifting theorems, inner product, BPP Lifting, Deterministic Lifting | |
| Seminar: | 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 04.07.2019 |
