Unifying computational entropies via KullbackLeibler divergence. We introduce KLhardness, a new notion of hardness for search problems which on the one hand is satisfied by all oneway functions and on the other hand implies both nextblock pseudoentropy and inaccessibleentropy, two forms of computational entropy used in recent constructions of pseudorandom generators and statistically hiding commitment schemes, respectively. Thus, KLhardness unifies the latter two notions of computational entropy and sheds light on the apparent duality between them. Additionally, it yields a more modular and illuminating proof that oneway functions imply nextblock inaccessible entropy, similar in structure to the proof that oneway functions imply nextblock pseudoentropy (Vadhan and Zheng, STOC u002712).

Towards a Reverse Newmans Theorem in Interactive Information Complexity Newmanu0027s theorem states that we can take any publiccoin communication protocol and convert it into one that uses only private randomness with but a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and convert it into one that only uses public randomness while preserving the information revealed to each player? We prove that the answer is yes, at least for protocols that use a bounded number of rounds. As an application, we prove new directsum theorems through the compression of interactive communication in the boundedround setting. To obtain this application, we prove a new oneshot variant of the SlepianWolf coding theorem, interesting in its own right. Furthermore, we show that if a Reverse Newmanu0027s Theorem can be proven in full generality, then full compression of interactive communication and fullygeneral directsum theorems will result.