License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.14
URN: urn:nbn:de:0030-drops-175172
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17517/
Beame, Paul ;
Koroth, Sajin
On Disperser/Lifting Properties of the Index and Inner-Product Functions
Abstract
Query-to-communication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated "lifted" function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. A number of important complexity questions could be resolved if we could make substantial improvements in the input size required for lifting with the Index function, which is a universal gadget for lifting, from its current near-linear size down to polylogarithmic in the number of inputs N of the original function or, ideally, constant. The near-linear size bound was recently shown by Lovett, Meka, Mertz, Pitassi and Zhang [Shachar Lovett et al., 2022] using a recent breakthrough improvement on the Sunflower Lemma to show that a certain graph associated with an Index function of that size is a disperser. They also stated a conjecture about the Index function that is essential for further improvements in the size required for lifting with Index using current techniques. In this paper we prove the following;
- The conjecture of Lovett et al. is false when the size of the Index gadget is less than logarithmic in N.
- The same limitation applies to the Inner-Product function. More precisely, the Inner-Product function, which is known to satisfy the disperser property at size O(log N), also does not have this property when its size is less than log N.
- Notwithstanding the above, we prove a lifting theorem that applies to Index gadgets of any size at least 4 and yields lower bounds for a restricted class of communication protocols in which one of the players is limited to sending parities of its inputs.
- Using a modification of the same idea with improved lifting parameters we derive a strong lifting theorem from decision tree size to parity decision tree size. We use this, in turn, to derive a general lifting theorem in proof complexity from tree-resolution size to tree-like Res(⊕) refutation size, which yields many new exponential lower bounds on such proofs.
BibTeX - Entry
@InProceedings{beame_et_al:LIPIcs.ITCS.2023.14,
author = {Beame, Paul and Koroth, Sajin},
title = {{On Disperser/Lifting Properties of the Index and Inner-Product Functions}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {14:1--14:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17517},
URN = {urn:nbn:de:0030-drops-175172},
doi = {10.4230/LIPIcs.ITCS.2023.14},
annote = {Keywords: Decision trees, communication complexity, lifting theorems, proof complexity}
}
|
Keywords: |
|
Decision trees, communication complexity, lifting theorems, proof complexity |
|
Collection: |
|
14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
01.02.2023 |
