The problem of guessing a chance variable (guessing problem for short) has seen applications in the context of cryptography, information measures, and data transmission. In this thesis, we introduce and solve four extensions of the guessing problem. Each extension is solved by a different, novel method that can be applied to a broad class of guessing problems. The first extension consists of a setting where two correlated memoryless sources each generate a sequence. A guesser seeks to only guess the first sequence, but, prior to guessing it, is allowed to produce guesses of the second. Given some ρ 0, we characterize the exponential growth rate (as the sequence length tends to infinity) of the least ρ-th moment of the number of guesses taken until the realization of the first sequence is known. We exhibit an asymptotically optimal guessing strategy which is a mixture of guessing strategies that either ignore the first sequence or guess it. We also offer an information-measure interpretation of our result. The second extension is similar to the first, but with k sources instead of two, and with the guesser seeking to guess every sequence. Unlike in the first extension, the guesser is not required to guess some sequences before others, and is assisted by a rate-limited helper that describes the sequences prior to guessing. We characterize the exponential growth rate of the least ρ-th moment of the number of guesses taken until all sequences are known. Our argument can be decomposed into two parts: first, a reduction of the guessing strategy to a data compression scheme that satisfies a number of desired properties; and second, using these properties in the construction of an asymptotically optimal guessing strategy. The third extension consists of two sources and two guessers: Guesser 1 seeks to guess the first sequence, and Guesser 2 the second. Prior to guessing, an encoder observes both sequences and produces three descriptions; the first two are revealed to Guesser 1, and the second two are revealed to Guesser 2 (each guesser is therefore revealed a common and a private description.) We characterize the set of all rate triples that allow the encoder to describe the sequences such that, for each guesser, the least ρ-th moment of the number of guesses does not exceed a given exponential. Building on our characterization of these rates, we follow Wyner’s approach and propose to define the Rényi Common Information as the least common description rate (of the message revealed to both guessers) under the constraint that the sum-rate be minimal. We characterize this quantity and show that it generalizes Wyner’s Common Information just as other Rényi information measures generalize Shannon’s. In the fourth and final extension, we again consider a two-sources setting. A guesser seeks to produce an approximate guess that must be close to the first sequence as measured by a given symbol-averaged distortion function. The guesser is assisted by a helper that reveals a rate-limited description of the second sequence prior to guessing. We characterize the exponential growth rate of the least ρ-th moment of the number of guesses taken until a valid approximation is produced. Our argument is based on a change-of-measure trick: Instead of working with the true probability measure, we construct a new one under which a previously constructed guessing strategy is shown to be asymptotically optimal.weiterlesen