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.33
URN: urn:nbn:de:0030-drops-175362
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17536/
Chattopadhyay, Arkadev ;
Mande, Nikhil S. ;
Sanyal, Swagato ;
Sherif, Suhail
Lifting to Parity Decision Trees via Stifling
Abstract
We show that the deterministic decision tree complexity of a (partial) function or relation f lifts to the deterministic parity decision tree (PDT) size complexity of the composed function/relation f∘g as long as the gadget g satisfies a property that we call stifling. We observe that several simple gadgets of constant size, like Indexing on 3 input bits, Inner Product on 4 input bits, Majority on 3 input bits and random functions, satisfy this property. It can be shown that existing randomized communication lifting theorems ([Göös, Pitassi, Watson. SICOMP'20], [Chattopadhyay et al. SICOMP'21]) imply PDT-size lifting. However there are two shortcomings of this approach: first they lift randomized decision tree complexity of f, which could be exponentially smaller than its deterministic counterpart when either f is a partial function or even a total search problem. Second, the size of the gadgets in such lifting theorems are as large as logarithmic in the size of the input to f. Reducing the gadget size to a constant is an important open problem at the frontier of current research.
Our result shows that even a random constant-size gadget does enable lifting to PDT size. Further, it also yields the first systematic way of turning lower bounds on the width of tree-like resolution proofs of the unsatisfiability of constant-width CNF formulas to lower bounds on the size of tree-like proofs in the resolution with parity system, i.e., Res(⊕), of the unsatisfiability of closely related constant-width CNF formulas.
BibTeX - Entry
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2023.33,
author = {Chattopadhyay, Arkadev and Mande, Nikhil S. and Sanyal, Swagato and Sherif, Suhail},
title = {{Lifting to Parity Decision Trees via Stifling}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {33:1--33:20},
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/17536},
URN = {urn:nbn:de:0030-drops-175362},
doi = {10.4230/LIPIcs.ITCS.2023.33},
annote = {Keywords: Decision trees, parity decision trees, lifting theorems}
}
|
Keywords: |
|
Decision trees, parity decision trees, lifting theorems |
|
Collection: |
|
14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
01.02.2023 |
