Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > INSTANCE OPTIMALITY:
Reports tagged with Instance Optimality:
TR21-152 | 8th November 2021
Gal Arnon, Tomer Grossman

Min-Entropic Optimality

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




ISSN 1433-8092 | Imprint