Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > INSTANCE COMPLEXITY:
Reports tagged with instance complexity:
TR19-113 | 5th September 2019
Tomer Grossman, Ilan Komargodski, Moni Naor

Instance Complexity and Unlabeled Certificates in the Decision Tree Model

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, ... more >>>




ISSN 1433-8092 | Imprint