Suppose that you want to check whether a graph satisfies some (graph) property. The goal is to minimize the number of queries to the adjacency matrix. You are given as an “untrusted hint” an isomorphic copy of the graph. You must always be correct, but the number of queries made is only measured when the hint is correct.
Do such unlabeled certificates help? In the worst case? Per instance?
We discuss labeled and unlabeled certificates in particular in the context of ``instance optimality". This 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). We study both deterministic and randomized decision trees and provide various characterizations and barriers for more general results. It turns out that randomized and deterministic instance optimality are incomparable. 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).
The instance optimality of the majority function is very sensitive wrt to the precise model and it varies widely between randomized, deterministic, unlabeled and unlabeled as a graph property.