BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Rank-Based Independence Testing in Near Linear Tim
e - Chaim Even-Zohar (Turing Institute)
DTSTART;TZID=Europe/London:20200305T143000
DTEND;TZID=Europe/London:20200305T153000
UID:TALK138481AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/138481
DESCRIPTION:In 1948 Hoeffding proposed a nonparametric test th
at detects dependence between two continuous rando
m variables (X\,Y)\, based on the ranking of n pai
red samples (Xi\,Yi). The computation of this comm
only-used test statistic requires O(n log n) time.
\n\nHoeffding's test is consistent against any dep
endent probability density f(x\,y)\, but can be fo
oled by other bivariate distributions with continu
ous margins.\nVariants of this test with stronger
consistency have been considered in works by Blum\
, Kiefer\, and Rosenblatt\, Yanagimoto\, and Bergs
ma and Dassios\, and others. The so far best known
algorithms to compute them have required quadrati
c time.\n\nWe present an algorithm that computes t
hese improved tests in time O(n log n). It is base
d on a new combinatorial approach for counting pat
tern 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
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR