BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//hacksw/handcal//NONSGML v1.0//EN
BEGIN:VEVENT
UID:node-3068192@mathematics.huji.ac.il
DTSTAMP:20211213T130000Z
DTSTART:20211213T130000Z
DTEND:20211213T150000Z
SUMMARY:Combinatorics: Ilan Newman (Haifa)
DESCRIPTION:**HUJI*Combinatorics Seminar*\n*\n*\n*When:*Monday December 13th, 2021, at 3PM (Israel time)\n*Where:*B400 in the CS\Engineering building\n*Speaker:*Ilan Newman (Haifa)\n*Title:*Strongly sublinear tests for patternfreeness in functions (or time \nseries)\n*Abstract:*\nFor a permutation $\pi:[k] \to [k]$, a function $f:[n] \to \R$\ncontains a $\pi$-appearance if there exists $1 \leq i_1 < i_2 < ...< i_k \leq \nn$\nsuch that for all $s,t \in [k]$, $f(i_s) < f(i_t)$ ifand only if $\pi(s) < \n\pi(t)$.\nWe say that the function $f$ is $\pi$-free if it has no\n$\pi$-appearances. In this paper, we investigate the problem of\ntesting whether an input function $f$ is $\pi$-free or whether at\nleast $\eps n$ values in $f$ need to be changed in order to make it\n$\pi$-free. This problem is a generalization of the well-studied\nmonotonicity testing and was first studied by Newman, Rabinovich,\nRajendraprasad and Sohler~\cite{NewmanRRS19}, followed by quite a few\nother papers. We show that for all constants $k \in \mathbb{N}$, $\eps\n\in (...
LOCATION:The link will be sent to you after registration
END:VEVENT
END:VCALENDAR