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.
--------
Question: 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.

Answer: On learning k-parities with and without noise


Question: Consider a weighted or unweighted k-nearest neighbor graph that has been built on n data points drawn randomly according to some density p on R. We study the convergence of the shortest path distance in such graphs as the sample size tends to infinity. We prove that for unweighted kNN graphs, this distance converges to an unpleasant distance function on the underlying space whose properties are detrimental to machine learning. We also study the behavior of the shortest path distance in weighted kNN graphs.

Answer: Shortest path distance in random k-nearest neighbor graphs


Question: Selectional preferences have long been claimed to be essential for coreference resolution. However, they are mainly modeled only implicitly by current coreference resolvers. We propose a dependencybased embedding model of selectional preferences which allows fine-grained compatibility judgments with high coverage. We show that the incorporation of our model improves coreference resolution performance on the CoNLL dataset, matching the state-of-the-art results of a more complex system. However, it comes with a cost that makes it debatable how worthwhile such improvements are.

Answer:
Revisiting Selectional Preferences for Coreference Resolution