BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Rank-Based Independence Testing in Near Linear Time - Chaim Even-Z
 ohar (Turing Institute)
DTSTART:20200305T143000Z
DTEND:20200305T153000Z
UID:TALK138481@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:In 1948 Hoeffding proposed a nonparametric test that detects d
 ependence between two continuous random variables (X\,Y)\, based on the ra
 nking of n paired samples (Xi\,Yi). The computation of this commonly-used 
 test statistic requires O(n log n) time.\n\nHoeffding's test is consistent
  against any dependent probability density f(x\,y)\, but can be fooled by 
 other bivariate distributions with continuous margins.\nVariants of this t
 est with stronger consistency have been considered in works by Blum\, Kief
 er\, and Rosenblatt\, Yanagimoto\, and Bergsma and Dassios\, and others. T
 he so far best known algorithms to compute them have required quadratic ti
 me.\n\nWe present an algorithm that computes these improved tests in time 
 O(n log n). It is based on a new combinatorial approach for counting patte
 rn occurrences in a given permutation\, which we call corner tree formulas
 \, and will be explained in the talk.\n\nJoint work with Calvin Leng\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR