  This paper presents new lower and upper bounds for the compression rate of
binary prefix codes optimized over memoryless sources according to various
nonlinear codeword length objectives. Like the most well-known redundancy
bounds for minimum average redundancy coding - Huffman coding - these are in
terms of a form of entropy and/or the probability of an input symbol, often the
most probable one. The bounds here, some of which are tight, improve on known
bounds of the form L in [H,H+1), where H is some form of entropy in bits (or,
in the case of redundancy objectives, 0) and L is the length objective, also in
bits. The objectives explored here include exponential-average length, maximum
pointwise redundancy, and exponential-average pointwise redundancy (also called
dth exponential redundancy). The first of these relates to various problems
involving queueing, uncertainty, and lossless communications; the second
relates to problems involving Shannon coding and universal modeling. For these
two objectives we also explore the related problem of the necessary and
sufficient conditions for the shortest codeword of a code being a specific
length.
