# New Distinguishers for Negation-Limited Weak Pseudorandom Functions

Zhihuai Chen  ,  Siyao Guo  ,  Qian Li  ,  Chengyu Lin  and  Xiaoming Sun
Institute of Computing Technology, Chinese Academy of Sciences. E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>and<EMAIL_ADDRESS> New York
University, Shanghai E-mail<EMAIL_ADDRESS> Columbia University E-mail:
<EMAIL_ADDRESS>
###### Abstract.

We show how to distinguish circuits with $\log k$ negations (a.k.a
$k$-monotone functions) from uniformly random functions in
$\exp\big{(}\tilde{O}\big{(}n^{1/3}k^{2/3}\big{)}\big{)}$ time using random
samples. The previous best distinguisher, due to the learning algorithm by
Blais, Cannone, Oliveira, Servedio, and Tan (RANDOM’15), requires
$\exp\big{(}\tilde{O}(n^{1/2}k)\big{)}$ time.

Our distinguishers are based on Fourier analysis on _slices of the Boolean
cube_. We show that some “middle” slices of negation-limited circuits have
strong low-degree Fourier concentration and then we apply a variation of the
classic Linial, Mansour, and Nisan “Low-Degree algorithm” (JACM’93) on slices.
Our techniques also lead to a slightly improved weak learner for negation
limited circuits under the uniform distribution.

##  1\. Introduction

One significant goal in the area of cryptography is to understand how simple
cryptography can be. This motivates the study of low complexity cryptography
which explores the possibility of implementing cryptographic primitives in low
complexity classes. This line of research inherently lies at the intersection
of computational complexity and cryptography. It links core problems in both
areas and has become an essential source of new perspectives for both areas.

In this work, we continue this line of research and focus on _pseudorandom
functions_ (PRFs) in _negation-limited computation_. We start by introducing
pseudorandom functions and negation-limited computation before connecting them
to explain the main motivation of our work.

Pseudorandom functions. Pseudorandom functions (PRFs) [11] are fundamental
primitives in symmetric cryptography. In particular, they yield direct
solutions to most central goals of symmetric cryptography, such as encryption,
authentication and identification. They are well studied in the theoretical
community and widely used in practice.

As lightweight (computationally limited) devices become popular, the
efficiency of cryptographic implementations also become increasingly
significant. To obtain a better tradeoff between efficiency and security, a
weaker notion of PRFs called _weak pseudorandom functions_ (See Definition
1.1) has been considered. A distinguisher for a weak PRFs aims to distinguish
a random member of the family from a truly random function after observing a
number of random samples $(x_{1},f_{s}(x_{1})),\dots,(x_{m},f_{s}(x_{m}))$
where $x_{1},\dots,x_{m}$ are independent uniformly random strings from
$\\{0,1\\}^{n}$ and $f_{s}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is the function in question. Weak
PRFs suffice for many key applications such as encryption and authentication
in symmetric cryptography. More importantly, weak PRFs may allow for
significant gains in efficiency. Akavia et al. [2] pointed out weak PRFs have
the potential to bypass the limitations of PRFs in low depth circuits. In
particular, they provided candidate weak PRFs in a class of low depth circuits
where PRFs provably cannot exist. This raises the following natural questions.

> Can weak PRFs bypass the limitations of PRFs in other low complexity
> classes?

Besides cryptography, another important motivation for the study of low
complexity PRFs comes from explaining the difficulties of obtaining circuit
lower bounds and learning algorithms. We refer interested readers to the
survey by Bogdanov and Rosen [6].

Negation-Limited Computation. The power of negations is a mystery in
complexity theory. One of the main difficulties in proving lower bounds on
circuit size using AND, OR, NOT gates is the presence of negation gates: the
best such lower bound is linear, whereas if no negation gates are allowed,
exponential lower bounds are known [21, 3, 1, 24, 7, 15]. In 1958, Markov [18]
observed that every Boolean (even multiple-output) function of $n$ variables
can be computed by a circuit with only $\log{n}$ negation gates. In other
words, the potential, possibly exponential, gap between monotone computation
and non-monotone computation exists due to as few as $\log{n}$ negations.

Besides circuit complexity, the divide between monotone and non-monotone
computation exists in general: while we usually have a fairly good
understanding of the monotone case, many things may fail to hold when negation
gates are allowed. Aiming at bridging the gap between monotone and non-
monotone computation, a body of recent work studies negation-limited
computation from multiple angles including learning [5], cryptography [14],
Boolean formulas [12, 22], property testing [8, 13], Boolean function
conjectures [17]. Although the above works extend many results in monotone
cases to as many as $O(\log n)$ negations, they also leave open several
surprisingly basic questions about a single negation ranging from weak
learning algorithms to the structure of their Fourier spectrum. More
surprisingly, in the context of property testing, a single negation can be
exponentially harder than the monotone case [8, 13]. Our understanding of a
single negation remains largely a mystery.

When the circuit size is not of interest, the classes of circuits with $\log
k$ negations are captured by the class of so-called $k$-monotone functions
where each function in the family can be written as the parity of $k$ monotone
function (See Section 2.1). To simplify the presentation, we will use
$k$-monotone functions instead of circuits with $\log{k}$ negations in some of
our discussions.

PRFs in Negation-Limited Computation. Can pseudorandom functions be computed
by a few negations? For pseudorandom functions, we have a fairly good
understanding. Guo et al. [14] showed that PRFs are inherently highly non-
monotone and require $\log{n}-O(1)$ negations, which is optimal up to an
additive constant. However, the answer to weak PRFs is unsatisfying. Guo et
al. [14] observed that weak PRFs cannot be monotone due to the weak learner
for monotone functions by Blum et al. [4]. For general $k$, the best
distinguisher, due to Blais et al. [5], runs in time $n^{O(k\sqrt{n})}$.
Therefore even for a single negation (_i.e._ , $k=2$), the best distinguisher
runs in time $n^{O(\sqrt{n})}$.

The above results demonstrate two strong separations. In negation-limited
computation, weak PRFs have the potential to be much simpler than PRFs: even a
single negation may have $n^{O(\sqrt{n})}$ hardness whereas PRFs cannot exist.
From the angle of weak PRFs, the hardness gap between even a single negation
and monotone can be as large as $n^{O(\sqrt{n})}$. These separations are our
main motivation to connect them together to study negation-limited weak PRFs.

###  1.1. Our Results

Before presenting our main results, we define _weak pseudorandom functions_
and _weak learning under uniform distribution_.

######  Definition 1.1 (Weak Pseudorandom Functions).

Let $S$ be a distribution over $\\{0,1\\}^{m}$ and
$\\{F_{s}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}\\}$ be a family of functions
indexed by string $s$ in the support of $S$. We say $\\{F_{s}\\}$ is a
$(c,\epsilon)$-secure weak pseudorandom functions (wPRFs) if for every (non-
uniform) algorithm $D$ that can be implemented by a circuit of size at most
$c$,

(1) $\displaystyle\mathinner{\\!\left\lvert\Pr_{s}[D^{F_{s}}\mbox{
accepts}]-\Pr_{R}[D^{R}\mbox{ accepts}]\right\rvert}\leq\varepsilon,$

where $s$ is distributed according to $S$, $R$ is a function sampled uniformly
at random from the set of all functions from $\\{0,1\\}^{n}$ to $\\{0,1\\}$,
and $D^{h}$ denotes the execution of $D$ with random oracle access to a
Boolean function $h\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}$. In other words, the
distinguisher $D^{h}$ only has access to random examples of the form
$(x,h(x))$ where $x$ is uniformly distributed over $\\{0,1\\}^{n}$. The two
probabilities in (1) are both also over the random samples $x$’s.

######  Definition 1.2 (Weak Learning under Uniform Distribution).

We say that an algorithm $A$ weakly learns a family of Boolean functions
$\mathcal{F}$ if $A$ can only access uniformly random samples, and $\forall
f\in\mathcal{F}$ it outputs a hypothesis $h$ such that with high probability
(over the random samples and the randomness of $A$)

$\Pr_{x\sim U_{\\{0,1\\}^{n}}}\left[f(x)\neq
h(x)\right]\leq\frac{1}{2}-\frac{1}{\text{poly}(n)},$

where $U_{\\{0,1\\}^{n}}$ is the uniform distribution over $\\{0,1\\}^{n}$.

A weak learner works slightly better than random guessing. But from this small
advantage, if it’s non-negligible, one can naturally derive an efficient
distinguisher against random function. Any weak learner explicitly gives an
attack on the weak pseudorandom functions candidates. Conversely, weak
pseudorandom functions are hard to learn. Our main result is new
distinguishers for negation-limited weak pseudorandom functions. Our results
hold for inefficient circuits and are stated in terms of $k$-monotone
functions.

######  Theorem 1.3.

Any family of $k$-monotone functions can be distinguished from uniformly
random functions in $\exp\left(O(n^{1/3}(k\log n)^{2/3})\right)$ time. In
other words, any family of $k$-monotone functions is not a
$\left(\exp\left(O(n^{1/3}(k\log n)^{2/3})\right),1/3\right)$-secure weak
pseudorandom family.

The previous best distinguisher for $k$-monotone weak PRFs is the learning
algorithm by Blais et al. [5] which runs in $\exp\big{(}O(n^{1/2}k\log
n)\big{)}$ time. Our result improves an $\Omega\big{(}n^{1/6}(k\log
n)^{1/3}\big{)}$ factor in the exponent.

Theorem 1.3 implies that exponentially secure weak PRFs requires
$\log{n}-O(\log\log{n})$ negations, which is optimal up to an additive
$O(\log\log{n})$ term. Therefore, weak PRFs cannot bypass the limitations of
PRFs in terms of achieving exponential security.

Theorem 1.3 also implies that $1$ negation functions can be distinguished in
$\exp\big{(}O(n^{1/3}\log^{2/3}{n})\big{)}$ time. Therefore, unlike testing
$1$ negation (using $1$-sided non-adaptive tester) [13] and learning $1$
negation to high accuracy [5], distinguishing $1$ negation doesn’t suffer from
the $\exp(\sqrt{n})$ barrier.

It is natural to ask if we can leverage the distinguisher to a learning
algorithm. Our second result gives weak learning algorithms for $k$-monotone
functions under the uniform distribution.

######  Theorem 1.4.

$k$-monotone functions are weakly learnable in time
$\exp\left(O\big{(}k\sqrt{n\log n}\big{)}\right)$.

Our result slightly improves the previous best weak learner due to Blais et
al. [5], by a $\Omega\big{(}\sqrt{\log n}\big{)}$ factor in the exponent.

We conjecture that both Theorems 1.3 and 1.4 are not tight. However, we
believe that any further improvement of our results, even for a single
negation, require completely new techniques or proving rather hard conjectures
which seem out of reach. See Section 6 for more details.

Our Techniques. Blais et al. [5] showed a Fourier concentration of
$k$-monotone functions on low degree monomials, by bounding the total
influence of $k$-monotone functions. Then they apply the “Low-Degree
Algorithm” established by Linial, Mansour, and Nisan [16] to learn
$k$-monotone functions. One natural idea to improve their learning algorithm
is to show Fourier concentration on lower levels. However, their influence
bound is tight and even for monotone functions, we cannot show concentration
bound on fewer than $\Omega(\sqrt{n})$ levels [9], which will require at least
$n^{\Omega(\sqrt{n})}$ time by applying the “Low-Degree Algorithm”.

Our main technique is using Fourier analysis on slices [10, 23]. Although the
Fourier concentration on the Boolean cube cannot be improved, we show some
“middle” slices of $k$-monotone functions can have much stronger Fourier
concentration. Then by adapting the “Low-Degree Algorithm” to the slices, we
obtain a distinguisher with significantly improved running time. Our weak
learner is a simple variant of the “Low-Degree Algorithm” on slices.

Fourier analysis on slices has a notion of total influence which allows us to
show Fourier concentration on a slice in a similar way. We give an upper bound
on the sum of total influences for all “middle” slices of any $k$-monotone
function. It implies the existence of a “middle” slice function with small
total influence, and therefore good concentration. Then we optimize the number
of “middle” slices to be analyzed to get an efficient algorithm.

Paper Organization. We begin with the basic notations in Section 2, then
present the structural results for $k$-monotone functions in Section 3. In
Sections 4 and 5, we present the distinguisher and weaker learner.

##  2\. Preliminaries

In this paper, all the logarithms are base 2.

###  2.1. Alternating Number, Negation Complexity, k-monotone Functions

For any two inputs $x,y\in\\{0,1\\}^{n}$, we say $x\prec y$ iff $x\neq y$ and
$x_{i}\leq y_{i}$ for all $i\in[n]$. A chain $X=(x^{1},x^{2},\dots,x^{\ell})$
of length $\ell$ is an increasing sequence of inputs in $\\{0,1\\}^{n}$ where
$x^{i}\prec x^{i+1}$ for $i\in[\ell-1]$. For a Boolean function
$f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, we
define the alternating number of $f$ on chain $X$ to be the number of value
flips on this chain:

$a(f,X)=\left|\\{i\in[\ell-1]\mathrel{\mathop{\mathchar 58\relax}}f(x^{i})\neq
f(x^{i+1})\\}\right|$

Let $\mathcal{C}$ be the set of all chains on $\\{0,1\\}^{n}$, the alternating
number of $f$ is

$a(f)=\max_{X\in\mathcal{C}}a(f,X)$

Note that the alternating number of a monotone function is no more than 1.

A celebrated result of Markov connects the alternating number of a Boolean
function $f$ to the negation complexity $\mathbb{N}(f)$ – the minimum number
of negation gates required in any Boolean $\sf{AND}-\sf{OR}$ circuits to
compute $f$.

######  Theorem 2.1 (Markov’s Theorem [18]).

Let $f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}$
be a function which is not identically $0$ with $f(0^{n})=0$, then
$\mathbb{N}(f)=\lceil\log\big{(}a(f)+1\big{)}\rceil-1$.

Blais et al. [5] showed decomposition for functions with low alternating
number [5].

######  Theorem 2.2 (Blais et al. [5]).

Let $f$ be a $k$-alternating function, then $f(x)=h(m_{1}(x),\dots,m_{k}(x))$
where $m_{i}(x)$ is monotone and h is the parity function or its negation.
Conversely, any function of this form is $k$-alternating.

The above characterization shows a simple structure for functions with a low
alternating number, which are computable by few negation gates. To simplify
notation, we’ll focus on the parity of few monotone functions.

######  Definition 2.3 ($k$-monotone function).

A function $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is said to be $k$-monotone, if
there exist $k$ monotone functions $g_{1},g_{2},\dots,g_{k}$ such that
$f=g_{1}\oplus g_{2}\oplus\cdots\oplus g_{k}$.

###  2.2. Orthogonal Basis for Functions over a Slice

Given a set of strings $A\subseteq{[n]\choose r}\mathrel{\mathop{\mathchar
58\relax}}=\\{(x_{1},\ldots,x_{n})\in\\{0,1\\}^{n}\mathrel{\mathop{\mathchar
58\relax}}\sum_{i}{x_{i}}=r\\}$, denote its density in this slice by $\mu(A)$,
_i.e._ , $\mu(A)=|A|/{n\choose r}$. Define its upper shadow as

$\partial^{+}A\mathrel{\mathop{\mathchar 58\relax}}=\\{x\in{[n]\choose
r+1}\mathrel{\mathop{\mathchar 58\relax}}x\succ y$ for some $y\in A\\}$,

and its lower shadow as

$\partial^{-}A\mathrel{\mathop{\mathchar 58\relax}}=\\{x\in{[n]\choose
r-1}\mathrel{\mathop{\mathchar 58\relax}}x\prec y$ for some $y\in A\\}$.

Filmus [10] and Srinivasan [23] independently introduced an orthogonal basis
for functions over a slice of the Boolean hypercube ${[n]\choose r}$, which
plays a central role in our proofs. All the following definitions can be found
in [10]. We present them here for the reader’s convenience.

######  Definition 2.4.

For $d\leq n/2$, a sequence of length $d$ is a sequence $S=s_{1},\ldots,s_{d}$
of distinct numbers in $[n]$. The set of all sequences of length $d$ is
denoted by $\mathcal{S}_{n,d}$, and the set of all sequences is denoted by
$\mathcal{S}_{n}$.

For any two disjoint sequences $A,B\in\mathcal{S}_{n,d}$ we define the
function $\chi_{A,B}$ as

$\chi_{A,B}=\prod_{i=1}^{d}(x_{a_{i}}-x_{b_{i}}).$

######  Definition 2.5.

For $d\leq n/2$, let $A,B\in\mathcal{S}_{n,d}$ be disjoint. We say that $A$ is
smaller than $B$, written $A<B$, if $a_{i}<b_{i}$ for all $i\in[d]$.
Similarly, we say that $A$ is at most $B$, written $A\leq B$, if $a_{i}\leq
b_{i}$ for all $i\in[d]$.

A sequence $B\in\mathcal{S}_{n}$ is a top set if $B$ is increasing and for
some disjoint sequence $A$ of the same length, $A<B$. The set of top sets of
length $d$ is denoted by $\mathcal{B}_{n,d}$, and the set of all top sets is
denoted by $\mathcal{B}_{n}$.

######  Definition 2.6.

For $B\in\mathcal{B}_{n,d}$, define

$\chi_{B}=\sum_{A\in\mathcal{S}_{n,d}\mathrel{\mathop{\mathchar
58\relax}}A<B}\chi_{A,B}.$

######  Theorem 2.7 (Filmus [10]).

Let $r\leq n/2$ be an integer, the set $\\{\chi_{B}\mathrel{\mathop{\mathchar
58\relax}}B\in\mathcal{B}_{n,d}$ for some $d\leq r\\}$ is an orthogonal basis
for the vector space of functions over the slice ${[n]\choose r}$. The Young-
Fourier expansion of $f\mathrel{\mathop{\mathchar 58\relax}}{[n]\choose
r}\rightarrow\mathbb{R}$ is the unique representation

$f=\sum_{B\in\mathcal{B}_{n,d},\ d\leq r}\hat{f}(B)\chi_{B},$

where $\hat{f}(B)=\frac{\langle f,\chi_{B}\rangle}{\|\chi_{B}\|_{2}^{2}}$.
Here $\langle f,g\rangle\mathrel{\mathop{\mathchar
58\relax}}=\mathbb{E}_{x\sim U}[f(x)g(x)]$. In addition for
$B\in\mathcal{B}_{n,d}$,

  1. (1)

$\|\chi_{B}\|_{2}^{2}=\prod_{i=1}^{d}\frac{(b_{i}-2(i-1))(b_{i}-2(i-1)-1)}{2}\cdot
2^{d}\frac{r^{\underline{d}}(n-r)^{\underline{d}}}{n^{\underline{2d}}}=n^{O(d)}$.
In particular, if $r\geq\frac{n}{4}$ and $d=o(n)$, then
$\|\chi_{B}\|_{2}^{2}\geq 2^{-O(d)}$. Here,
$r^{\underline{d}}=\prod_{i=0}^{d-1}(r-i)$.

  2. (2)

$\|\chi_{B}\|_{\infty}\leq\sum_{A\in\mathcal{S}_{n,d}\mathrel{\mathop{\mathchar
58\relax}}A<B}\|\chi_{A,B}\|_{\infty}=n^{O(d)}$.

By Boolean duality, we can extend the above Young-Fourier expansion to where
$r>n/2$ naturally. This can be done by replacing the basis $\\{\chi_{B}(x)\\}$
by $\\{\chi_{\bar{B}}(x)\mathrel{\mathop{\mathchar
58\relax}}=\chi_{B}(\bar{x})\\}$ where $\bar{x}$ is obtained by flipping all
bits of $x$.

######  Corollary 2.8.

Let $r>n/2$ be an integer, the set
$\\{\chi_{\bar{B}}(x)\mathrel{\mathop{\mathchar
58\relax}}B\in\mathcal{B}_{n,d}$ for some $d\leq n-r\\}$ is an orthogonal
basis for the vector space of functions over the slice ${[n]\choose r}$. The
Young-Fourier expansion of $f\mathrel{\mathop{\mathchar 58\relax}}{[n]\choose
r}\rightarrow\mathbb{R}$ is the unique representation

$f=\sum_{B\in\mathcal{B}_{n,d},\ d\leq n-r}\hat{f}(B)\chi_{\bar{B}},$

where $\hat{f}(B)=\frac{\langle
f,\chi_{\bar{B}}\rangle}{\|\chi_{\bar{B}}\|_{2}^{2}}$. In addition, we have
$\|\chi_{\bar{B}}\|_{2}^{2}=\|\chi_{B}\|_{2}^{2}$ and
$\|\chi_{\bar{B}}\|_{\infty}=\|\chi_{B}\|_{\infty}$.

Like functions over the Boolean hypercube, we can define the total weight on
level $d$:

######  Definition 2.9.

Let $f\mathrel{\mathop{\mathchar 58\relax}}{[n]\choose
r}\rightarrow\mathbb{R}$, for any $r\leq n$, define

$\mathbb{W}^{d}(f)=\sum_{B\in\mathcal{B}_{n,d}}\hat{f}(B)^{2}\|\chi_{B}\|_{2}^{2},$

and denote $\mathbb{W}^{>d}(f)=\sum_{d^{\prime}>d}\mathbb{W}^{d}$ and
$\mathbb{W}^{\leq d}(f)=\sum_{d^{\prime}\leq d}\mathbb{W}^{d}$.

######  Definition 2.10.

Let $f\mathrel{\mathop{\mathchar 58\relax}}{[n]\choose r}\rightarrow\\{\pm
1\\}$. For $i,j\in[n]$, define the influence of $f$ on the pair $(i,j)$ as

$\mathbb{I}_{ij}[f]=2\Pr[f(x^{(i,j)})\neq f(x)].$

Here $x^{(i,j)}$ is obtained by switching $x_{i}$ and $x_{j}$. The total
influence of $f$ is

$\mathbb{I}[f]=\frac{1}{n}\sum_{1\leq i<j\leq n}\mathbb{I}_{ij}[f].$

######  Lemma 2.11 (O’Donnell and Wimmer [20]).

Let $f\mathrel{\mathop{\mathchar 58\relax}}{[n]\choose r}\rightarrow\\{\pm
1\\}$ and $A=\\{x\in{[n]\choose r}\mathrel{\mathop{\mathchar
58\relax}}f(x)=-1\\}$, then

$\min\\{\mu(\partial^{+}A),\mu(\partial^{-}A)\\}\geq\mu(A)+\frac{n}{4r(n-r)}\cdot\mathbb{I}[f]\geq\mu(A)+\frac{1}{n}\mathbb{I}[f].$

######  Theorem 2.12 (Filmus [10]).

Let $f\mathrel{\mathop{\mathchar 58\relax}}{[n]\choose r}\rightarrow\\{\pm
1\\}$. Then

$\mathbb{I}[f]=\sum_{d\leq\min(r,n-r)}\frac{d(n+1-d)}{n}\cdot\mathbb{W}^{d}=\sum_{B\in\mathcal{B}_{n,d},d\leq\min(r,n-r)}\frac{d(n+1-d)}{n}\cdot\hat{f}(B)^{2}\|\chi_{B}\|_{2}^{2}.$

In addition, according to Parseval’s identity,

$\sum_{d}\mathbb{W}^{d}=\sum_{B\in\mathcal{B}_{n,d},d\leq\min(r,n-r)}\hat{f}(B)^{2}\|\chi_{B}\|_{2}^{2}=\|f\|_{2}^{2}=1.$

###  2.3. Basic Inequalities

Finally, we will make use of the Hoeffding bound.

######  Theorem 2.13 (Hoeffding Bound).

Let $X=\sum_{i=1}^{n}X_{i}$, where $X_{i}\in[a_{i},b_{i}]$ are independent
random variables. Then for any $\theta>0$,

$\Pr(|X-\mathbb{E}(X)|\geq\theta)\leq
2\exp\left(-\frac{2\theta^{2}}{\Sigma_{i}(b_{i}-a_{i})^{2}}\right).$

######  Corollary 2.14.

Let $X$ be a random variable with distribution $\mathcal{D}$ whose range is
$[l,u]$. Let $X_{1},\ldots,X_{m}$ be its independent samples. Then w.p.
$1-\delta$, for any $\epsilon>0$,

$\mathinner{\\!\left\lvert\frac{1}{m}\sum_{i=1}^{m}X_{i}-\mathbb{E}(X)\right\rvert}\leq\epsilon$

as long as $m\geq(u-l)^{2}\log(2/\delta)/(2\epsilon^{2})$.

The following fact will also be used.

######  Proposition 2.15.

For $t=o(n)$, ${n\choose n/2-t/2}/2^{n}=\frac{1}{\sqrt{n}}\cdot
2^{-O(t^{2}/n)}$.

###### Proof.

By Stirling’s approximation,

$\log{n\choose
n/2-t/2}=\log(1+o(1))+\log\sqrt{\frac{n}{2\pi(n/2-t/2)(n/2+t/2)}}+n\cdot
H\left(\frac{n/2-t/2}{n}\right),$

where $H(p)=-p\log p-(1-p)\log(1-p)$ is the binary entropy function. As
$t/2n=o(1)$, by the Taylor expansion of the entropy function around $1/2$, we
have

$H\left(\frac{1}{2}-\frac{t}{2n}\right)=1-\frac{1+o(1)}{2\ln
2}\left(\frac{t}{n}\right)^{2}.$

The conclusion follows immediately. ∎

##  3\. Concentration Property of $k$-Monotone Functions

In the rest of this paper, for a function $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, we convert the range to $\\{\pm
1\\}$. The mapping from $\\{0,1\\}$ to $\\{-1,1\\}$ is given by $1-2b$,
sending $0$ to $1$ and $1$ to $-1$. So a function $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\rightarrow\\{\pm 1\\}$ is said to be $k$-monotone if
$(1-f)/2$ is $k$-monotone.

In this section, we show some “middle” slice of a $k$-monotone function has
Fourier concentration. For functions $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\rightarrow\\{\pm 1\\}$, let $f|_{r}$ be the
subfunction of $f$ restricted to ${[n]\choose r}$ and
$\mu(f|_{r})\mathrel{\mathop{\mathchar 58\relax}}=\mu(f|_{r}^{-1}(-1))$.

######  Definition 3.1 ($(t,d,\epsilon)$-concentration).

We say $f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\rightarrow\\{\pm
1\\}$ is $(t,d,\epsilon)$-concentrated if the following holds: for some $r$
such that $n/2-t/2\leq r\leq n/2+t/2$,

$\mathbb{W}^{>d}(f|_{r})=\sum_{B\in\mathcal{B}_{n,d^{\prime}}\mathrel{\mathop{\mathchar
58\relax}}d^{\prime}>d}\widehat{f|_{r}}(B)^{2}\|\chi_{B}\|_{2}^{2}<\epsilon.$

Intuitively, $f$ has low-degree Fourier concentration on at least one of the
middle slices.

######  Lemma 3.2.

Let $f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\rightarrow\\{\pm
1\\}$ be a $k$-monotone function. For any $1<t\leq n$ and any $d$, $\epsilon$
such that $d\epsilon\geq 2kn/t$, $f$ is $(t,d,\epsilon)$-concentrated.

Lemma 3.2 follows from an upper bound on the sum of total influences on
slices.

######  Proposition 3.3.

Let $f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\rightarrow\\{\pm
1\\}$ be a $k$-monotone function. Then $\sum_{r=0}^{n-1}\mathbb{I}[f|_{r}]\leq
kn$.

We first prove Lemma 3.2 using Proposition 3.3.

###### Proof of Lemma 3.2.

By contradiction, we assume that
$\mathbb{W}^{>d}(f|_{r})\geq\epsilon\geq\frac{2kn}{d(t-1)}$ for any
$n/2-t/2\leq r\leq n/2+t/2$. According to Proposition 3.3, we have
$\sum_{r=\lceil n/2-t/2\rceil}^{\lfloor n/2+t/2\rfloor}\mathbb{I}[f|_{r}]\leq
kn$. By averaging, let $n/2-t/2\leq r\leq n/2+t/2$ be such that
$\mathbb{I}[f|_{r}]\leq kn/t$. By Theorem 2.12, we can deduce that,

$\displaystyle\frac{kn}{t}\geq\mathbb{I}[f|_{r}]$
$\displaystyle=\sum_{d^{\prime}\leq\min(r,n-r)}\frac{d^{\prime}(n+1-d^{\prime})}{n}\cdot\mathbb{W}^{d^{\prime}}(f|_{r})$
$\displaystyle\geq\sum_{d<d^{\prime}\leq\min(r,n-r)}\frac{d^{\prime}(n+1-d^{\prime})}{n}\cdot\mathbb{W}^{d^{\prime}}(f|_{r})$
$\displaystyle\geq\frac{d(n+1-d)}{n}\cdot\sum_{d<d^{\prime}\leq\min(r,n-r)}\mathbb{W}^{d^{\prime}}(f|_{r})$
$\displaystyle>\frac{d}{2}\cdot\epsilon\geq\frac{d}{2}\cdot\frac{2kn}{dt}\geq\frac{kn}{t}\;,$

a contradiction. ∎

Now we prove Proposition 3.3.

###### Proof of Proposition 3.3.

Suppose $f$ is the parity of $h_{1},\cdots,h_{k}$ where each $h_{i}$ is
monotone. For any $r$, when we switch $x_{i}$ and $x_{j}$, $f|_{r}(x)$ changes
only if at least one $h_{i}|_{r}(x)$ changes for $i=1,2,\dots,k$. Thus,
combining with the union bound, we have

(2) $\displaystyle\mathbb{I}[f|_{r}]\leq\sum_{i=1}^{k}\mathbb{I}[h_{i}|_{r}].$

Since $h_{i}$ is monotone, the upper shadow of $h_{i}|^{-1}_{r}(-1)$ is a
subset of $h_{i}|^{-1}_{r+1}(-1)$. Then according to Lemma 2.11, we have

$\mu(h_{i}|_{r+1})\geq\mu(h_{i}|_{r})+\frac{1}{n}I(h_{i}|_{r}),$

which implies

(3)
$\displaystyle\frac{1}{n}\sum_{r=0}^{n-1}\mathbb{I}[h_{i}|_{r}]\leq\mu(h_{i}|_{n})-\mu(h_{i}|_{0})\leq
1.$

Inequalities (2) and (3) imply the desired conclusion. ∎

##  4\. Distinguishers for $k$-monotone Functions

In this section, we prove the following theorem.

See 1.3

We prove this theorem by giving a distinguisher for $(t,d,1/2)$-concentrated
functions.

######  Proposition 4.1.

For $t\leq n/4$ and $d=o(n/\log n)$, any family of $(t,d,1/2)$-concentrated
functions can be distinguished from uniform random functions in $2^{O(d\log
n+t^{2}/n)}$ time.

By Lemma 3.2, every $k$-monotone function is
$\left((kn^{2}\log{n})^{1/3},4\big{(}\frac{k^{2}n}{\log
n}\big{)}^{1/3},1/2\right)$-concentrated, then Theorem 1.3 follows. Now we
prove the proposition.

###### Proof.

The distinguisher is given in Algorithm 1. We’ll show that

  * •

(Soundness) It accepts a uniform random function w.p. $o(1)$;

  * •

(Completeness) It accepts any $(t,d,1/2)$-concentrated function w.p. $1-o(1)$;

  * •

(Complexity) Its sample/time complexity is $2^{O(d\log n+t^{2}/n)}$.

1

2Let $C$ be a large enough constant;

3 for  _$r\leftarrow\lceil\frac{n}{2}-\frac{t}{2}\rceil$ to
$\lfloor\frac{n}{2}+\frac{t}{2}\rfloor$_ do

4 $S\leftarrow 0$;

5 for  _$B\in\mathcal{B}_{n,d^{\prime}}$ with $d^{\prime}\leq d$_ do

6 if  _$r\leq n/2$_ then

7 Estimate $\langle f|_{r},\chi_{B}\rangle$ with accuracy $n^{-C\cdot d}$;

8 $S\leftarrow S+\widehat{f|_{r}}(B)^{2}\|\chi_{B}\|_{2}^{2}$;

// $\widehat{f|_{r}}(B)^{2}\|\chi_{B}\|_{2}^{2}=\langle
f|_{r},\chi_{B}\rangle^{2}/\|\chi_{B}\|_{2}^{2}$

9

10 else

11 Estimate $\langle f|_{r},\chi_{\bar{B}}\rangle$ with accuracy $n^{-C\cdot
d}$;

12 $S\leftarrow S+\widehat{f|_{r}}(\bar{B})^{2}\|\chi_{\bar{B}}\|_{2}^{2}$;

// $\widehat{f|_{r}}(B)^{2}\|\chi_{\bar{B}}\|_{2}^{2}=\langle
f|_{r},\chi_{\bar{B}}\rangle^{2}/\|\chi_{\bar{B}}\|_{2}^{2}$

13

14

15 if  _$S\geq 3/8$_ then

16 Return True;

17

18Return False;

19

Algorithm 1 A Distinguisher for $(t,d,1/2)$-Concentrated Functions

Soundness. Let $f$ be a uniform random function. We claim that for each
$\frac{n}{2}-\frac{t}{2}\leq r\leq\frac{n}{2}+\frac{t}{2}$, the variable $S$
in Line 11 is at most $1/4$ w.p. $1-o(\frac{1}{n})$, which concludes the
soundness by the union bound.

Fix such an $r$. W.l.o.g., we assume that $r\leq n/2$. For any
$B\in\mathcal{B}_{n,d^{\prime}}$ where $d^{\prime}\leq d$, it is easily seen
that $\operatorname*{\mathbb{E}}_{f}\big{[}\langle
f|_{r},\chi_{B}\rangle\big{]}=0$, then by the Hoeffding bound,

$\Pr_{f}\left[\left|\langle f|_{r},\chi_{B}\rangle\right|\geq\theta\right]\leq
2\exp\left(-2\theta^{2}{n\choose r}\big{/}\|\chi_{B}\|^{2}_{2}\right)\leq
2\exp\left(-\theta^{2}\left(\frac{4}{3}\right)^{n/4-o(n)}\right),$

where the last inequality is due to that ${n\choose
r}\geq(\frac{n}{r})^{r}\geq(\frac{4}{3})^{n/4}$ and
$\|\chi_{B}\|^{2}_{2}=2^{O(d\log n)}=(\frac{4}{3})^{o(n)}$. In particular, by
letting $\theta=\left(\frac{3}{4}\right)^{n/10}$ and using the union bound, we
have that with probability at least
$1-n^{O(d)}\cdot\exp\left(-\theta^{2}\left(\frac{4}{3}\right)^{n/4-o(n)}\right)=1-o(\frac{1}{n})$,
$\big{|}\langle f|_{r},\chi_{B}\rangle\big{|}<\theta$ for every
$B\in\mathcal{B}_{n,d^{\prime}}$ where $d^{\prime}\leq d$. Thus, w.p.
$1-o(\frac{1}{n})$,

$\displaystyle\mathbb{W}^{\leq d}[f|_{r}]$
$\displaystyle=\sum_{B\in\mathcal{B}_{n,d^{\prime}},d^{\prime}\leq
d}\widehat{f|_{r}}(B)^{2}\|\chi_{B}\|_{2}^{2}=\sum_{B\in\mathcal{B}_{n,d^{\prime}},d^{\prime}\leq
d}\frac{\langle
f|_{r},\chi_{B}\rangle^{2}}{\|\chi_{B}\|_{2}^{2}}\leq\sum_{B\in\mathcal{B}_{n,d^{\prime}},d^{\prime}\leq
d}\frac{\theta^{2}}{\|\chi_{B}\|_{2}^{2}}\leq\frac{1}{8},$

where the last inequality holds for sufficiently large $n$. Finally, $S$ is an
estimate of $\mathbb{W}^{\leq d}[f|_{r}]$ with additive error
$n^{-\Omega(d)}$.

Completeness. Let $f$ be a $(t,d,1/2)$-concentrated function. By definition,
there is some $r$ such that $n/2-t/2\leq r\leq n/2+t/2$ and $W^{\leq
d}[f|_{r}]>1/2$. As $S$ is an estimate of $\mathbb{W}^{\leq d}[f|_{r}]$ with
additive error $n^{-\Omega(d)}$, we conclude that Algorithm 1 accepts $f$ with
high probability.

Complexity. The loop in Line 2 is repeated at most $t$ times. In Line 4, the
number of strings $B\in\mathcal{B}_{n}$ of length at most $d$ we enumerated is
at most $n^{O(d)}$. Furthermore, for each $n/2-t/2\leq r\leq n/2+t/2$ and each
$B\in\mathcal{B}$ of size $\leq d$, according to the Hoeffding bound,
$n^{O(d)}$ uniform random samples on the slice ${[n]\choose r}$ are sufficient
to estimate $\langle f|_{r},\chi_{B}\rangle$ with accuracy $n^{-C\cdot d}$. In
addition, a random uniform sample is from the slice ${[n]\choose r}$ with
probability ${n\choose r}/2^{n}$, which is $\frac{1}{\sqrt{n}}\cdot
2^{-O(t^{2}/n)}$ according to Proposition 2.15. Thus, the total number of
random samples used is at most $t\cdot n^{O(d)}\cdot n^{O(d)}\cdot
2^{O(t^{2}/n)}=2^{O(d\log n+t^{2}/n)}$.

Besides, the function
$\chi_{B}=\sum_{A\in\mathcal{S}_{n,d}\mathrel{\mathop{\mathchar
58\relax}}A<B}\chi_{A,B}$ can be computed by enumerating all $n^{O(d)}$
strings $A$ in $\mathcal{S}_{n,d}$. Thus, the time complexity is also
$2^{O(d\log n+t^{2}/n)}$. ∎

##  5\. Weak Learners for $k$-monotone Functions

In this section, we prove the following theorem.

See 1.4

We prove Theorem 1.4 by giving a weak learner for $(t,d,1/2)$-concentrated
functions. By Lemma 3.2, $k$-monotone functions are $\left(\sqrt{n\log
n},4k\sqrt{\frac{n}{\log n}},1/2\right)$-concentrated, then Theorem 1.4
follows.

######  Proposition 5.1.

For $t=O(\sqrt{n\log n})$ and $d=o(n/\log n)$, Algorithm 2 weakly learns
$(t,d,1/2)$-concentrated functions in $2^{O(d\log n+t^{2}/n)}$ time.

To learn $(t,d,1/2)$-concentrated functions $f$, Algorithm 2 tries to find out
the slice ${[n]\choose r}$ on which $f|_{r}$ is concentrated, and then figures
out a function $g\mathrel{\mathop{\mathchar 58\relax}}{[n]\choose
r}\rightarrow\mathbb{R}$ which is very close to $f|_{r}$. To convert the
approximated function $g$ to a Boolean-valued function, we can utilize Claim
5.2 similar to Exercise 3.34 in [19]. For the rest of the slices, the learner
just outputs the most frequent value. Since $t=O(\sqrt{n\log n})$, each slice
in $[n/2-t/2,n/2+t/2]$ is at least a $\frac{1}{\sqrt{n}}\cdot
2^{-O(t^{2}/n)}=1/\text{poly}(n)$ fraction according to Proposition 2.15.
Hence we get a $(1/2-1/\text{poly}(n))$-close function $h$.

1 Let $C$ be a large enough constant;

2 for  _$r\leftarrow\frac{n}{2}-\frac{t}{2}$ to $\frac{n}{2}+\frac{t}{2}$_ do

3 $S\leftarrow 0$;

4 $p\leftarrow 1$;

5 for  _$B\in\mathcal{B}_{n,d^{\prime}}$ with $d^{\prime}\leq d$_ do

6 if  _$r\leq n/2$_ then

7 Estimate $\langle f|_{r},\chi_{B}\rangle$ with accuracy $n^{-C\cdot d}$;

8 $S\leftarrow S+\widehat{f|_{r}}(B)^{2}\|\chi_{B}\|_{2}^{2}$;

9

10 else

11 Estimate $\langle f|_{r},\chi_{\bar{B}}\rangle$ with accuracy $n^{-C\cdot
d}$;

12 $S\leftarrow S+\widehat{f|_{r}}(B)^{2}\|\chi_{\bar{B}}\|_{2}^{2}$;

13

14

15 if  _$S\geq 3/8$_ then

16 if  _$r\leq n/2$_ then

17
$g(x)\leftarrow\sum_{B\in\mathcal{B}_{n,d^{\prime}}\mathrel{\mathop{\mathchar
58\relax}}d^{\prime}\leq d}\widehat{f|_{r}}(B)\chi_{B}(x)$;

18

19 else

20
$g(x)\leftarrow\sum_{B\in\mathcal{B}_{n,d^{\prime}}\mathrel{\mathop{\mathchar
58\relax}}d^{\prime}\leq d}\widehat{f|_{r}}(B)\chi_{\bar{B}}(x)$;

21

22

23 while  _$p >\sqrt{3}/4$_ do

24 Pick $\theta\in[-1,1]$ uniformly at random;

25 Estimate $p\leftarrow\Pr[f|_{r}\neq\mbox{sgn}(g-\theta)]$;

26

27 Estimate $\mu_{\neq r}\leftarrow\mathbb{E}_{x}[f(x)\mid|x|\neq r]$;

28

29 Return $h(x)=\begin{cases}\mbox{sgn}(g(x)-\theta)&\mbox{if }|x|=r;\\\
\mbox{sgn}(\mu_{\neq r})&\mbox{if }|x|\neq r.\end{cases}$

30

Return $h(x)\equiv 0$.

Algorithm 2 A weak learner for $(t,d,1/2)$-concentrated functions

###### Proof of Proposition 5.1.

We first show that Algorithm 2 weakly learns $(t,d,1/2)$-concentrated
functions. Let $f$ be a $(t,d,1/2)$-concentrated function. For each
$n/2-t/2\leq r\leq n/2+t/2$, the variable $S$ in Line 12 is an estimate of
$\mathbb{W}^{\leq d}[f|_{r}]$ with additive error $n^{-\Omega(d)}$. Then for
some $r^{\star}$, the condition $S\geq 3/8$ in Line 12 holds, and Algorithm 2
executes Lines 13-21. For the function $g$ obtained in Line 14 or Line 16, and
sufficiently large $n$,

$\displaystyle||f|_{r^{\star}}-g||_{1}\leq||f|_{r^{\star}}-g||_{2}=\sqrt{\sum_{B\in\mathcal{B}_{n,d^{\prime}},d^{\prime}\leq
d}{(\widehat{f|_{r}}(B)-\hat{g}(B))^{2}}\|\chi_{B}\|_{2}^{2}+W^{>d}[f|_{r^{\star}}]}\leq\sqrt{o(1)+5/8}\leq\sqrt{3}/2.$

To convert $g$ to a Boolean-valued function, we utilize the following claim.

######  Claim 5.2.

Suppose $f\mathrel{\mathop{\mathchar 58\relax}}{[n]\choose
r}\rightarrow\\{-1,1\\}$ and $g\mathrel{\mathop{\mathchar
58\relax}}{[n]\choose r}\rightarrow\mathbb{R}$. Pick $\theta\in[-1,1]$
uniformly at random and define
$g^{\prime}=\mbox{sgn}\big{(}g(x)-\theta\big{)}$, we have
$\mathbb{E}_{\theta}\left[\Pr_{x}\big{(}f(x)\neq
g^{\prime}(x)\big{)}\right]\leq\|f-g\|_{1}/2$.

###### Proof.

By rewriting the last formula and swapping the expectation operators, we have

$\displaystyle\operatorname*{\mathbb{E}}_{\theta}\left[\Pr_{x}\big{(}f(x)\neq
g^{\prime}(x)\big{)}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{\theta}\operatorname*{\mathbb{E}}_{x}\left[1_{f(x)\neq
g^{\prime}(x)}\right]=\operatorname*{\mathbb{E}}_{x}\operatorname*{\mathbb{E}}_{\theta}\left[1_{f(x)\neq
g^{\prime}(x)}\right]=\operatorname*{\mathbb{E}}_{x}\left[\Pr_{\theta}\big{(}f(x)\neq\mbox{sgn}(g(x)-\theta)\big{)}\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x}\left[\frac{|f(x)-g(x)|}{2}\right]=\frac{\|f-g\|_{1}}{2}.\qed$

Thus, for a random $\theta\in[-1,1]$,
$\Pr\big{[}f|_{r}(x)\neq\mbox{sgn}(g(x)-\theta)\big{]}\leq\sqrt{3}/4$ holds
with a constant probability. That is, with high probability, the loop of Lines
17-19 is repeated a constant number of times, and we will get a
$\theta^{\star}$ such that
$\Pr\big{[}f|_{r}(x)\neq\mbox{sgn}(g(x)-\theta^{\star})\big{]}\leq\sqrt{3}/4$.
Finally, we have

$\displaystyle\Pr[h(x)\neq f(x)]=$ $\displaystyle\Pr[|x|\neq
r]\Pr[f(x)\neq\mbox{sgn}(\mu_{\neq r})\mid|x|\neq
r]+\Pr[|x|=r]\Pr\big{[}f|_{r}(x)\neq\mbox{sgn}(g(x)-\theta^{\star})\big{]}$
$\displaystyle\leq$ $\displaystyle\left(1-\frac{{n\choose
r}}{2^{n}}\right)\cdot\frac{1}{2}+\frac{{n\choose
r}}{2^{n}}\cdot\frac{\sqrt{3}}{4}=\frac{1}{2}+\frac{{n\choose
r}}{2^{n}}\cdot\left(\frac{\sqrt{3}}{4}-\frac{1}{2}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2}-\left(\frac{1}{2}-\frac{\sqrt{3}}{4}\right)\cdot\frac{1}{\sqrt{n}}\cdot
2^{-O(t^{2}/n)}=\frac{1}{2}-\frac{1}{\mbox{poly}(n)},$

where the second last equality is according to Proposition 2.15 and the last
equality is due to that $t=O(\sqrt{n\log n})$.

What remains is to show that Algorithm 2 terminates in $2^{O(d\log
n+t^{2}/n)}$ time. First, as shown in the analysis of Algorithm 1, for each
$n/2-t/2\leq r\leq n/2+t/2$, it costs $2^{O(d\log n+t^{2}/n)}$ time to execute
Lines 5-11. For $r^{\star}$, Algorithm 2 would execute Lines 13-21. As shown
above, the loop of Lines 17-19 is repeated a constant of times. So, it costs
$2^{O(d\log n+t^{2}/n)}$ time to execute Lines 13-21. Therefore the total time
complexity is $t\cdot 2^{O(d\log n+t^{2}/n)}=2^{O(d\log n+t^{2}/n)}$. ∎

##  6\. Discussion and Open Problems

Fourier analysis on slices. It is surprising to us that a simple variant of
the “Low-Degree Algorithm” on slices can outperform the classic “Low-Degree
Algorithm” in terms of attacking negation-limited weak PRFs. To the best of
our knowledge, unlike Fourier analysis on the Boolean cube, Fourier analysis
on slices has not been explored in cryptography. It is an extremely
interesting direction to use this technique to attack more cryptographic
constructions, particularly ones which are secure against attacks based on
standard Fourier analysis.

The hardness of $1$ negation weak PRFs. One of the most intriguing open
problems is how hard can $1$ negation weak PRFs be? Our bound suggests that,
unlike testing $1$ negation (using a 1-sided non-adaptive tester) [13] and
learning $1$ negation to high accuracy [5], distinguishing $1$ negation is
significantly more efficient than $2^{O(\sqrt{n})}$. Can we have polynomial
time distinguishers? We believe that new structural results of $2$-monotone
functions are required for polynomial time distinguishers.

Fourier spectrum of $k$-monotone functions on low levels. It is a basic fact
[19] that every monotone function $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ has a large Fourier coefficient
on the first two levels. Does a similar statement hold for $k$-monotone
functions? In particular, we are curious about the following conjecture.

######  Conjecture 6.1.

Let $f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}$
be a $k$-monotone function. There exists a set $S\subseteq[n]$ of size at most
$k$ such that $|\hat{f}(S)|=1/\mathrm{poly}(n)$.

Conjecture 6.1 immediately implies an efficient weak learner (and an efficient
distinguisher) for $k$-monotone functions. In fact, our first attempt to
distinguish $k$-monotone is to prove Conjecture 6.1. So far, even the
following much weaker conjecture remains open.

######  Conjecture 6.2.

Let $f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}$
be a $2$-monotone function. There exists a set $S\subseteq[n]$ of size
$o(\sqrt{n})$ such that $|\hat{f}(S)|>0$.

Acknowledgments. We sincerely thank the anonymous reviewers for their detailed
and constructive comments. We thank Shengyu Zhang for fruitful discussions at
the early stage of this work. Siyao Guo would like to thank Igor Carboni
Oliveira for telling her Conjectures 6.1 and Conjecture 6.2.

## References

  * AB [87] Noga Alon and Ravi B Boppana.  The monotone circuit complexity of boolean functions.  Combinatorica, 7(1):1–22, 1987.
  * ABG+ [14] Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen.  Candidate weak pseudorandom functions in $AC^{0}\circ MOD_{2}$.  In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 251–260. ACM, 2014.
  * And [85] Alexander E Andreev.  On a method for obtaining lower bounds for the complexity of individual monotone functions.  Doklady Akademii Nauk SSSR, 282:1033–1037, 1985.
  * BBL [98] Avrim Blum, Carl Burch, and John Langford.  On learning monotone boolean functions.  In Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on, pages 408–415. IEEE, 1998.
  * BCO+ [15] Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang Tan.  Learning circuits with few negations.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, pages 512–527, 2015.
  * BR [17] Andrej Bogdanov and Alon Rosen.  Pseudorandom functions: Three decades later.  In Tutorials on the Foundations of Cryptography., pages 79–158. 2017.
  * BU [99] Christer Berg and Staffan Ulfberg.  Symmetric approximation arguments for monotone lower bounds without sunflowers.  Computational Complexity, 8(1):1–20, 1999.
  * CGG+ [17] Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer.  Testing $k$-monotonicity.  In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, pages 29:1–29:21, 2017\.
  * DSFT+ [15] Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, and Karl Wimmer.  Approximate resilience, monotonicity, and the complexity of agnostic learning.  In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 498–511. Society for Industrial and Applied Mathematics, 2015.
  * Fil [16] Yuval Filmus.  An orthogonal basis for functions over a slice of the boolean hypercube.  Electr. J. Comb., 23(1):P1.23, 2016.
  * GGM [86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali.  How to construct random functions.  Journal of the ACM, 33(4):792–807, 1986.
  * GK [17] Siyao Guo and Ilan Komargodski.  Negation-limited formulas.  Theoretical Computer Science, 660:75–85, 2017.
  * GKW [19] Elena Grigorescu, Akash Kumar, and Karl Wimmer.  Flipping out with many flips: Hardness of testing $k$-monotonicity.  SIAM J. Discret. Math., 33(4):2111–2125, 2019.
  * GMOR [15] Siyao Guo, Tal Malkin, Igor C Oliveira, and Alon Rosen.  The power of negations in cryptography.  In Theory of Cryptography Conference, pages 36–65. Springer, 2015\.
  * HR [00] Danny Harnik and Ran Raz.  Higher lower bounds on monotone size.  In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 378–387. ACM, 2000.
  * LMN [93] Nathan Linial, Yishay Mansour, and Noam Nisan.  Constant depth circuits, Fourier transform, and learnability.  Journal of the ACM (JACM), 40(3):607–620, 1993.
  * LZ [17] Chengyu Lin and Shengyu Zhang.  Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers.  In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 51:1–51:13, 2017.
  * Mar [58] Andrey A Markov.  On the inversion complexity of a system of functions.  Journal of the ACM (JACM), 5(4):331–334, 1958.
  * O’D [14] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * OW [09] Ryan O’Donnell and Karl Wimmer.  KKL, Kruskal-Katona, and monotone nets.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 725–734, 2009.
  * Raz [85] Alexander A Razborov.  Lower bounds for the monotone complexity of some boolean functions.  In Soviet Math. Dokl., volume 31, pages 354–357, 1985.
  * Ros [15] Benjamin Rossman.  Correlation bounds against monotone $NC^{1}$.  In LIPIcs-Leibniz International Proceedings in Informatics, volume 33. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.
  * Sri [11] Murali K Srinivasan.  Symmetric chains, Gelfand–Tsetlin chains, and the Terwilliger algebra of the binary Hamming scheme.  Journal of Algebraic Combinatorics, 34(2):301–322, 2011.
  * Tar [88] Éva Tardos.  The gap between monotone and non-monotone circuit complexity is exponential.  Combinatorica, 8(1):141–142, 1988.