TASK DEFINITION: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
PROBLEM: We first consider the problem of learning k-parities in the on-line mistake-bound model: given a hidden vector x {0, 1} with |x| = k and a sequence of "questions" a1, a2, {0, 1} , where the algorithm must reply to each question with ai, x (mod 2), what is the best tradeoff between the number of mistakes made by the algorithm and its time complexity? We improve the previous best result of Buhrman et. al. [BGM10] by an exp(k) factor in the time complexity. Second, we consider the problem of learning k-parities in the presence of classification noise of rate (0, 1/2). A polynomial time algorithm for this problem (when > 0 and k = (1)) is a longstanding challenge in learning theory. Grigorescu et al. [GRV11] showed an algorithm running in time ( n k/2 )1+4+o(1) . Note that this algorithm inherently requires time ( n k/2 ) even when the noise rate is polynomially small. We observe that for sufficiently small noise rate, it is possible to break the ( n k/2 ) barrier. In particular, if for some function f(n) = (1) and [1/2, 1), k = n/f(n) and = o(f(n)/ log n), then there is an algorithm for the problem with running time poly(n) ( n k )1 e.

SOLUTION: On learning k-parities with and without noise

PROBLEM: We study the problem of identifying the best action among a set of possible options when the value of each action is given by a mapping from a number of noisy micro-observables in the so-called fixed confidence setting. Our main motivation is the application to the minimax game search, which has been a major topic of interest in artificial intelligence. In this paper we introduce an abstract setting to clearly describe the essential properties of the problem. While previous work only considered a two-move game tree search problem, our abstract setting can be applied to the general minimax games where the depth can be non-uniform and arbitrary, and transpositions are allowed. We introduce a new algorithm (LUCB-micro) for the abstract setting, and give its lower and upper sample complexity results. Our bounds recover some previous results, which were only available in more limited settings, while they also shed further light on how the structure of minimax problems influence sample complexity.

SOLUTION: Structured Best Arm Identification with Fixed Confidence

PROBLEM: This paper introduces a new computing model based on the cooperation among Turing machines called orchestrated machines. Like universal Turing machines, orchestrated machines are also designed to simulate Turing machines but they can also modify the original operation of the included Turing machines to create a new layer of some kind of collective behavior. Using this new model we can define some interested notions related to cooperation ability of Turing machines such as the intelligence quotient or the emotional intelligence quotient for Turing machines.

SOLUTION:
Are there intelligent Turing machines?