期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We introduce the notion of \emph{Min-Entropic Optimality} thereby providing a framework for arguing that a given algorithm computes a function better than any other algorithm. An algorithm is k(n) Min-Entropic Optimal if for every distribution D with min-entropy at least k(n), its expected running time when its input is drawn from D is at most a multiplicative constant larger than the expected running time (also with respect to D) of any other algorithm that computes the same function. Min-Entropic Optimality is a relaxation of the well established notion of instance optimality (when k(n)=0). Thereby, Min-Entropic Optimality provides a meaningful notion of optimality, even in scenarios where instance optimality is inherently impossible to achieve (for instance, in the super-linear regime). We analyze basic properties of this notion and prove that for many values of k(n) there exist functions that have Min-Entropic Optimal algorithms. We further show that some natural search problems, such as k-sum, are unlikely to have optimal algorithms under this notion.
