  We study the heavy hitters and related sparse recovery problems in the
low-failure probability regime. This regime is not well-understood, and has
only been studied for non-adaptive schemes. The main previous work is one on
sparse recovery by Gilbert et al.(ICALP'13). We recognize an error in their
analysis, improve their results, and contribute new non-adaptive and adaptive
sparse recovery algorithms, as well as provide upper and lower bounds for the
heavy hitters problem with low failure probability.
