Date:

Mon, 13/12/202115:00-17:00

**HUJI**Combinatorics Seminar

**When:**Monday December 13th, 2021, at 3PM (Israel time)

**Where:**B400 in the CS\Engineering building

**Speaker:**Ilan Newman (Haifa)

**Title:**Strongly sublinear tests for pattern freeness in functions (or time series)

**Abstract:**

For a permutation $\pi:[k] \to [k]$, a function $f:[n] \to \R$

contains a $\pi$-appearance if there exists $1 \leq i_1 < i_2 < ... < i_k \leq n$

such that for all $s,t \in [k]$, $f(i_s) < f(i_t)$ if and only if $\pi(s) < \pi(t)$.

We say that the function $f$ is $\pi$-free if it has no

$\pi$-appearances. In this paper, we investigate the problem of

testing whether an input function $f$ is $\pi$-free or whether at

least $\eps n$ values in $f$ need to be changed in order to make it

$\pi$-free. This problem is a generalization of the well-studied

monotonicity testing and was first studied by Newman, Rabinovich,

Rajendraprasad and Sohler~\cite{NewmanRRS19}, followed by quite a few

other papers. We show that for all constants $k \in \mathbb{N}$, $\eps

\in (0,1)$, and permutation $\pi:[k] \to [k]$, there is a one-sided

error $\eps$-testing algorithm for $\pi$-freeness of functions $f:[n]

\to \R$ that makes $\tilde{O}(n^{o(1)})$ queries. This improves

significantly upon the previous best upper bound $O(n^{1 - 1/(k-1)})$

by Ben-Eliezer and Canonne~\cite{Ben-EliezerC18}.

Our algorithm is adaptive, while the earlier best upper bound is known

to be tight for nonadaptive algorithms.

This is a joint work with Nithin Varma.