ECCC-Report TR21-152https://eccc.weizmann.ac.il/report/2021/152Comments and Revisions published for TR21-152en-usTue, 09 Nov 2021 13:01:40 +0200
Paper TR21-152
| Min-Entropic Optimality |
Tomer Grossman,
Gal Arnon
https://eccc.weizmann.ac.il/report/2021/152We 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.Tue, 09 Nov 2021 13:01:40 +0200https://eccc.weizmann.ac.il/report/2021/152