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.

[Q]: 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.
[A]: On learning k-parities with and without noise


[Q]: In this paper we present an Action Language-Answer Set Programming based approach to solving planning and scheduling problems in hybrid domains domains that exhibit both discrete and continuous behavior. We use action language H to represent the domain and then translate the resulting theory into an A-Prolog program. In this way, we reduce the problem of finding solutions to planning and scheduling problems to computing answer sets of A-Prolog programs. We cite a planning and scheduling example from the literature and show how to model it in H. We show how to translate the resulting H theory into an equivalent A-Prolog program. We compute the answer sets of the resulting program using a hybrid solver called EZCSP which loosely integrates a constraint solver with an answer set solver. The solver allows us reason about constraints over reals and compute solutions to complex planning and scheduling problems. Results have shown that our approach can be applied to any planning and scheduling problem in hybrid domains.
[A]: Planning and Scheduling in Hybrid Domains Using Answer Set Programming


[Q]: We present a method for learning treewidthbounded Bayesian networks from data sets containing thousands of variables. Bounding the treewidth of a Bayesian greatly reduces the complexity of inferences. Yet, being a global property of the graph, it considerably increases the difficulty of the learning process. We propose a novel algorithm for this task, able to scale to large domains and large treewidths. Our novel approach consistently outperforms the state of the art on data sets with up to ten thousand variables.
[A]:
Learning Bounded Treewidth Bayesian Networks with Thousands of Variables