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: Resume. Le crowdsourcing, un enjeu economique majeur, est le fait d'externaliser une tache interne d'une entreprise vers le grand-public, la foule. C'est ainsi une forme de sous-traitance digitale destinee a toute personne susceptible de pouvoir realiser la tache demandee generalement rapide et non automatisable. L'evaluation de la qualite du travail des participants est cependant un probleme majeur en crowdsourcing. En effet, les contributions doivent etre controlees pour assurer l'efficacite et la pertinence d'une campagne. Plusieurs methodes ont ete proposees pour evaluer le niveau d'expertise des participants. Ce travail a la particularite de proposer une methode de calcul de degres d'expertise en presence de donnees dont l'ordre de classement est connu. Les degres d'expertise sont ensuite consideres sur des donnees sans ordre pre-etabli. Cette methode fondee sur la theorie des fonctions de croyance tient compte des incertitudes des reponses et est evaluee sur des donnees reelles d'une campagne realisee en 2016.

SOLUTION: Une mesure d'expertise pour le crowdsourcing

PROBLEM: Joint attention is a core, early-developing form of social interaction. It is based on our ability to discriminate the third party objects that other people are looking at. While it has been shown that people can accurately determine whether another person is looking directly at them versus away, little is known about human ability to discriminate a third person gaze directed towards objects that are further away, especially in unconstraint cases where the looker can move her head and eyes freely. In this paper we address this question by jointly exploring human psychophysics and a cognitively motivated computer vision model, which can detect the 3D direction of gaze from 2D face images. The synthesis of behavioral study and computer vision yields several interesting discoveries. (1) Human accuracy of discriminating targets 8-10 of visual angle apart is around 40% in a free looking gaze task; (2) The ability to interpret gaze of different lookers vary dramatically; (3) This variance can be captured by the computational model; (4) Human outperforms the current model significantly. These results collectively show that the acuity of human joint attention is indeed highly impressive, given the computational challenge of the natural looking task. Moreover, the gap between human and model performance, as well as the variability of gaze interpretation across different lookers, require further understanding of the underlying mechanisms utilized by humans for this challenging task. * Tao Gao and Daniel Harari contributed equally to this work. When Computer Vision Gazes at Cognition Tao Gao, Daniel Harari , Joshua Tenenbaum, Shimon Ullman Center for Brains, Minds and Machines, Massachusetts Institute of Technology, Cambridge, MA Weizmann Institute of Science, Rehovot, Israel

SOLUTION:
When Computer Vision Gazes at Cognition