We analyze the general version of the classic guessing game Mastermind with n positions and k colors. Since the case k ≤ n 1 − ε , ε > 0 a constant, is well understood, we concentrate on larger numbers of colors. For the most prominent case k = n , our results imply that Codebreaker can find the secret code with O ( n log log n ) guesses. This bound is valid also when only black answer pegs are used. It improves the O ( n log n ) bound first proven by Chvátal. We also show that if both black and white answer pegs are used, then the O ( n log log n ) bound holds for up to n 2 log log n colors. These bounds are almost tight, as the known lower bound of Ω( n ) shows. Unlike for k ≤ n 1 − ε , simply guessing at random until the secret code is determined is not sufficient. In fact, we show that an optimal nonadaptive strategy (deterministic or randomized) needs Θ( n log n ) guesses.

We analyze the general version of the classic guessing game Mastermind with n positions and k colors. Since the case k ≤ n1−ε, ε > 0 constant, is well understood, we concentrate on larger numbers of colors. For the most prominent case k = n, our results imply that Codebreaker can find the secret code with O(n log log n) guesses. This bound is valid also when only black answer-pegs are used. It improves the O(n log n) bound first proven by Chvátal (Combinatorica 3 (1983), 325–329). We also show that if both black and white answer-pegs are used, then the O(n log log n) bound holds for up to n2 log log n colors. These bounds are almost tight as the known lower bound of Ω(n) shows. Unlike for k ≤ n1−ε, simply guessing at random until the secret code is determined is not sufficient. In fact, we show that any non-adaptive strategy needs an expected number of Ω(n log n) guesses.

Consider the following probabilistic one-player game: The board is a graph with $n$ vertices, which initially contains no edges. In each step, a new edge is drawn uniformly at random from all nonedges and is presented to the player, henceforth called Painter. Painter must assign one of $r$ available colors to each edge immediately, where $r\geq 2$ is a fixed integer. The game is over as soon as a monochromatic copy of some fixed graph $F$ has been created, and Painter's goal is to “survive” for as many steps as possible before this happens. We present a new technique for deriving upper bounds on the threshold of this game, i.e., on the typical number of steps Painter will survive with an optimal strategy. More specifically, we consider a deterministic two-player variant of the game where the edges are chosen not randomly, but by a second player Builder. However, Builder has to adhere to the restriction that, for some real number $d$, the ratio of edges to vertices in all subgraphs of the evolving board never exceeds $d$. We show that the existence of a winning strategy for Builder in this deterministic game implies an upper bound of $n^{2-1/d}$ for the threshold of the original probabilistic game. Moreover, we show that the best bound that can be derived in this way is indeed the threshold of the game if $F$ is a forest. We illustrate these general results with several examples. The technique proposed here has been used by Balogh and Butterfield [Discrete Math., 310 (2010), pp. 3653--3657] to derive the first nontrivial upper bounds for the threshold of the game where $F$ is a triangle and more than two colors are available.

We study the problem of creating a copy of some fixed graph H in the Achlioptas process on n vertices with parameter r, where $r=r(n)$ is a growing function of n. We prove general upper and lower bounds on the threshold of this problem, and derive exact threshold functions for the case where H is a tree, a cycle, or the complete graph on four vertices.

Genetic programming (GP) is a very successful type of learning algorithm that is hard to understand from a theoretical point of view. With this paper we contribute to the computational complexity analysis of genetic programming that has been started recently. We analyze GP in the well-known PAC learning framework and point out how it can observe quality changes in the the evolution of functions by random sampling. This leads to computational complexity bounds for a linear GP algorithm for perfectly learning any member of a simple class of linear pseudo-Boolean functions. Furthermore, we show that the same algorithm on the functions from the same class finds good approximations of the target function in less time.

Consider the following generalized notion of graph coloring: a coloring of the vertices of a graph G is valid w.r.t. some given graph F if there is no copy of F in G whose vertices all receive the same color. We study the problem of computing valid colorings of the binomial random graph Gn,p on n vertices with edge probability p = p(n) in the following online setting: the vertices of an initially hidden instance of Gn,p are revealed one by one (together with all edges leading to previously revealed vertices) and have to be colored immediately and irrevocably with one of r available colors. It is known that for any fixed graph F and any fixed integer r ≥ 2 this problem has a threshold p0 (F, r, n) in the following sense: For any function p(n) = o(p0) there is a strategy that a.a.s. (asymptotically almost surely, i.e., with probability tending to 1 as n tends to infinity) finds an r-coloring of Gn,p that is valid w.r.t. F online, and for any function p(n) = ω(p0) any online strategy will a.a.s. fail to do so. In this work we establish a general correspondence between this probabilistic problem and a deterministic two-player game in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. This characterization allows us to compute, for any F and r, a value γ = γ(F, r) such that the threshold of the probabilistic problem is given by p0(F, r, n) = n−γ. Our approach yields polynomial-time coloring algorithms that a.a.s. find valid colorings of Gn,p online in the entire regime below the respective thresholds, i.e., for any p(n) = o(n−γ).