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.