{'fraction_non_alphanumeric': 0.023539668700959023, 'fraction_numerical': 0.0017436791630340018, 'mean_word_length': 4.930232558139535, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Tradeoffs Between Computational Complexity and Information Content

In this dissertation, we study trade-offs between computational complexity and information content of problems arising in different facets of theoretical computer science. In the first part of the dissertation, we study the information content of online problems. For the online Steiner tree problem, we give matching upper and lower bounds on the advice complexity of the problem for the entire range of advice bits and thus resolve the problem. Then, we continue to study the randomness complexity of the disjoint path allocation problem. Our result shows that, in some cases, it is possible to use random bits instead of advice bits, while maintaining the same performance of the algorithm. In light of previous work on the power of advice bits for this problem, our algorithm is optimal. The second part of the dissertation is devoted to constructions of cryptographic primitives, focusing on constructions of a universal one-way hash function from a one-way function. First, we relate the regularity assumptions made about the one-way function to the efficiency of the construction, measured by the number of calls it makes to the one-way function. Qualitatively speaking, the stronger the assumptions about the structure of the underlying one-way function are, the better the performance of the construction is. We then study the limits of black-box constructions for this task, which, loosely speaking, are constructions that only use the functionality of the one-way function, but not its description. Since their introduction by Naor and Yung (STOC, 1989) twenty-five years ago, no lower bound on the number of calls to the one-way function such a construction has to make was known other than the trivial one of a single call. We give a first lower bound of an almost-linear number of calls. Moreover, if the function is regular, our bound is tight. Finally, in the last part of the dissertation, we continue the study of a recently introduced model of communication complexity with advice. We establish that the equality problem admits a protocol of polylogarithmic communication, provided a laconic advice of just one bit. For the divisibility problem, we design a protocol with sublinear communication and advice.