Information complexity is one of the most powerful tools to prove information-theoretical lower bounds, with broad applications in communication complexity and streaming algorithms. A core notion in information complexity analysis is the Shannon entropy. Though it has some convenient properties, such as chain rules, Shannon entropy still has inherent limitations. One of the most notable barriers is the square-root loss, which is reflected by the square-root gap between entropy gaps and statistical distances, e.g., Pinsker's inequality.

To break this barrier, we introduce a new method based on min-entropy analysis. Building on this new method, we prove the following three results.

1. A tight $\Omega(n/k)$ randomized lower bounds of the $k$-party Tree Pointer Jumping problems, improving an $\Omega(n/k^2)$ lower bounds by Chakrabarti, Cormode, and McGregor (STOC 08).
2. An $\Omega(n/k+\sqrt{n})$ lower bounds of the Chained Index problem for oblivious communication protocols, improving an $\Omega(n/k^2)$ lower bound by Cormode, Dark, and Konrad (ICALP 19). Here, oblivious means that the length of each message does not depend on the input.
3. An $\Omega(n/k-k)$ lower bounds of the Chained Index problem for non-oblivious protocols. To the best of our knowledge, this is the first lower bound for non-oblivious protocols.

Since both problems served as hard problems for numerous applications for streaming problems, our new lower bounds improve these streaming lower bounds directly.

On the technical side, unlike Shannon entropy, min-entropy does not have nice properties such as chain rules. To address this issue, we adopt the structure-vs-pseudorandomness decomposition used by Göös, Pitassi, and Watson (FOCS 17) and Yang and Zhang (STOC 24), where both papers used this decomposition to prove communication lower bounds. In this paper, we extend this method into streaming settings, contributing a new toolkit for proving streaming lower bounds.