License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.56
URN: urn:nbn:de:0030-drops-117418
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11741/
Grossman, Tomer ;
Komargodski, Ilan ;
Naor, Moni
Instance Complexity and Unlabeled Certificates in the Decision Tree Model
Abstract
Instance complexity is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively.
We initiate the systematic study of instance complexity and optimality in the query model (a.k.a. the decision tree model). In this model, instance optimality of an algorithm for computing a function is the requirement that the complexity of an algorithm on any input is at most a constant factor larger than the complexity of the best correct algorithm. That is we compare the decision tree to one that receives a certificate and its complexity is measured only if the certificate is correct (but correctness should hold on any input). We study both deterministic and randomized decision trees and provide various characterizations and barriers for more general results.
We introduce a new measure of complexity called unlabeled-certificate complexity, appropriate for graph properties and other functions with symmetries, where only information about the structure of the graph is known to the competing algorithm. More precisely, the certificate is some permutation of the input (rather than the input itself) and the correctness should be maintained even if the certificate is wrong. First we show that such an unlabeled certificate is sometimes very helpful in the worst-case. We then study instance optimality with respect to this measure of complexity, where an algorithm is said to be instance optimal if for every input it performs roughly as well as the best algorithm that is given an unlabeled certificate (but is correct on every input). We show that instance optimality depends on the group of permutations in consideration. Our proofs rely on techniques from hypothesis testing and analysis of random graphs.
BibTeX - Entry
@InProceedings{grossman_et_al:LIPIcs:2020:11741,
author = {Tomer Grossman and Ilan Komargodski and Moni Naor},
title = {{Instance Complexity and Unlabeled Certificates in the Decision Tree Model}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {56:1--56:38},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11741},
URN = {urn:nbn:de:0030-drops-117418},
doi = {10.4230/LIPIcs.ITCS.2020.56},
annote = {Keywords: decision tree complexity, instance complexity, instance optimality, query complexity, unlabeled certificates}
}
|
Keywords: |
|
decision tree complexity, instance complexity, instance optimality, query complexity, unlabeled certificates |
|
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
06.01.2020 |
