Chakraborty's function

Definition

Let [math]k[/math] be an integer. The Chakraborty pattern is a sequence of [math]k^2[/math] bits of the following form:

[math]\underbrace{11(-1)^{k-2}}_{k}\underbrace{11111\{-1,1\}^{k-5}}_{k}\underbrace{11111\{-1,1\}^{k-5}}_{k}\ldots \underbrace{11111\{-1,1\}^{k-5}}_{k} \underbrace{11111\{-1,1\}^{k-8}111}_k.[/math]

In other words, the [math]k^2[/math] bits are divided into [math]k[/math] blocks of size [math]k[/math]. In the first block, the first two bits are 1 and the rest are -1; in all the rest of the blocks, the first 5 bits are 1; and in the last block, the last three bits are 1 as well.

Let [math]n[/math] be such that [math]k^2 \leq n[/math]. The Chakraborty function [math]f:\{-1,1\}^n[/math] returns 1 if and only if the Chakraborty pattern is found as a substring of the [math]n[/math] bits, wrapping around if needed (that is, the function treats the input bits as if they sit on a circle).

Properties

• Chakraborty's function has 0-sensitivity [math]s_0(f) = \Theta(\frac{n}{k^2})[/math] and 1-sensitivity [math]s_1(f) = \Theta(k)[/math]. Thus, when [math]k = n^{1/3}[/math], the sensitivity of [math]f[/math] is [math]\Theta(n^{1/3})[/math]. When [math]k = n^{1/2}[/math], then [math]s_0(f) s_1(f) = \Theta(n^{1/2})[/math]. This is the smallest sensitivity possible for minterm-transitive functions.
• Chakraborty's function has block sensitivity and certificate complexity of order [math]\Theta(\max{k, n/k})[/math].