Authors Zhihuai Chen, Siyao Guo, Qian Li, Chengyu Lin, Xiaoming Sun,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19
www.theoryofcomputing.org
New Distinguishers for Negation-Limited
Weak Pseudorandom Functions
Zhihuai Chen Siyao Guo∗ Qian Li† Chengyu Lin‡
Xiaoming Sun§
Received March 13, 2021; Revised August 1, 2022; Published July 29, 2024
Abstract. We show how to distinguish circuits with log 𝑘 negations (a.k.a. 𝑘-
monotone functions) from uniformly random functions in exp 𝑂 𝑛 𝑘 ˜ 1/3 2/3
time
using random samples. The previous best distinguisher, due to the learning
algorithm by Blais, Canonne, Oliveira, Servedio, and Tan (RANDOM’15), requires
˜
exp 𝑂(𝑛 𝑘) time.
1/2
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.
∗ Supported by National Natural Science Foundation of China Grant No.62102260, NYTP Grant No. 20121201 and
NYU Shanghai Boost Fund.
† Supported by Hetao Shenzhen-Hong Kong Science and Technology Innovation Cooperation Zone Project
(No.HZQSWS-KCCYB-2024016), and the National Natural Science Foundation of China Grants No. 62002229.
‡ Supported in part by the U.S. Department of Energy (DOE), Office of Science, Office of Advanced Scientific
Computing Research under award number DE-SC-0001234, by a grant from the Columbia-IBM center for Blockchain
and Data Transparency, by JPMorgan Chase & Co., and by LexisNexis Risk Solutions. Any views or opinions
expressed herein are solely those of the authors listed.
§ Supported by the National Natural Science Foundation of China Grants No. 62325210.
ACM Classification: F.2,G.2
AMS Classification: 68Q25,68Q32
Key words and phrases: pseudorandom functions, negation-limited circuits, Fourier analysis
© 2024 Zhihuai Chen, Siyao Guo, Qian Li, Chengyu Lin, and Xiaoming Sun
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2024.v020a002
Z HIHUAI C HEN , S IYAO G UO , Q IAN L I , C HENGYU L IN , AND X IAOMING S UN
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) [12] 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 cryp-
tographic implementations also becomes 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 family of weak PRFs aims to
distinguish a random member of the family from a truly random function after observing
a number of random samples (𝑥 1 , 𝑓𝑠 (𝑥 1 )), . . . , (𝑥 𝑚 , 𝑓𝑠 (𝑥 𝑚 )) where 𝑥 1 , . . . , 𝑥 𝑚 are independent
uniformly random strings from {0, 1} 𝑛 and 𝑓𝑠 : {0, 1} 𝑛 → {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. [1] 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 [7].
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 [23, 3, 2, 26, 4, 16]. In 1958, Markov [20]
observed that every Boolean (even multiple-output) function of 𝑛 variables can be computed by
a circuit with only log 𝑛 negation gates. In other words, the exponential gap between monotone
computation and non-monotone computation exists due to as few as log 𝑛 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
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 2
N EW D ISTINGUISHERS FOR N EGATION -L IMITED W EAK P SEUDORANDOM F UNCTIONS
between monotone and non-monotone computation, a body of recent work studies negation-
limited computation from multiple angles including learning [5], cryptography [15], Boolean
formulas [14, 24], property testing [8, 13], Boolean function conjectures [18]. Although the
above works extend many results in monotone cases to as many as 𝑂(log 𝑛) 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 𝑘 negations are captured
by the class of so-called 𝑘-monotone functions where each function in the family can be written
as the parity of 𝑘 monotone functions (see Section 2.2). To simplify the presentation, we will use
𝑘-monotone functions instead of circuits with log 𝑘 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. [15]
showed that PRFs are inherently highly non-monotone and require log 𝑛 − 𝑂(1) negations, which
is optimal up to an additive constant. However, the answer to weak PRFs is unsatisfying. Guo
et al. [15] observed that weak PRFs cannot be monotone due to the weak learner for monotone
functions √by Blum et al. [6]. For general 𝑘, the best distinguisher, due to Blais et al. [5], runs in
time 𝑛 𝑂(𝑘√ 𝑛) . Therefore even for a single negation (i. e., 𝑘 = 2), the best distinguisher runs in
time 𝑛 𝑂( 𝑛) .
The above results demonstrate two strong separations. In negation-limited computation,
weak PRFs have the potential
√
to be much simpler than PRFs: for all we know, even a single
negation may have 𝑛 Ω( 𝑛) hardness whereas PRFs cannot exist. From the angle of weak PRFs, √
the hardness gap between even a single negation and monotone could be as large as 𝑛 Ω( 𝑛) .
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 𝑆 be a distribution over {0, 1} 𝑚 and
{𝐹𝑠 : {0, 1} 𝑛 → {0, 1}} be a family of functions indexed by string 𝑠 in the support of 𝑆. We say
that {𝐹𝑠 } is a family of (𝑐, 𝜖)-secure weak pseudorandom functions (wPRFs) if for every Boolean
circuit 𝐷 of size at most 𝑐,
Pr[𝐷 𝐹𝑠 accepts] − Pr[𝐷 𝑅 accepts] ≤ 𝜀, (1.1)
𝑠 𝑅
where 𝑠 is distributed according to 𝑆, 𝑅 is a function sampled uniformly at random from the set
of all functions from {0, 1} 𝑛 to {0, 1}, and 𝐷 ℎ denotes the execution of 𝐷 with random oracle
access to a Boolean function ℎ : {0, 1} 𝑛 → {0, 1}. In other words, the distinguisher 𝐷 ℎ only has
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 3
Z HIHUAI C HEN , S IYAO G UO , Q IAN L I , C HENGYU L IN , AND X IAOMING S UN
access to random examples of the form (𝑥, ℎ(𝑥)) where 𝑥 is uniformly distributed over {0, 1} 𝑛 .
The two probabilities in Equation (1.1) are both also over the random samples 𝑥.
Definition 1.2 (Weak learning under the uniform distribution). We say that an algorithm 𝐴
weakly learns a family ℱ of Boolean functions under the uniform distribution, if given any
𝑓 ∈ ℱ it accesses pairs (𝑥, 𝑓 (𝑥)) where 𝑥 is picked from {0, 1} 𝑛 uniformly at random, and then
outputs a hypothesis ℎ such that with high probability (over the random samples and the
randomness of 𝐴)
1 1
𝑓 (𝑥) ≠ ℎ(𝑥) ≤ −
Pr (1.2)
𝑥∼𝑈{0,1} 𝑛 2 poly(𝑛)
where 𝑈{0,1}𝑛 is the uniform distribution over {0, 1} 𝑛 .
A weak learner works slightly better than random guessing. But from this small advantage, if
it is non-negligible, one can naturally derive an efficient distinguisher against a random function.
Any weak learner explicitly gives an attack on candidate families of weak pseudorandom
functions. Conversely, families of weak pseudorandom functions are hard to learn. Our main
result is new distinguishers for negation-limited families of weak pseudorandom functions.
Our results hold for inefficient circuits and are stated in terms of 𝑘-monotone functions.
family of 𝑘-monotone
Theorem 1.3. Any functions can be distinguished from uniformly random
functions in exp 𝑂(𝑛 1/3 (𝑘 log 𝑛)2/3 ) time. In other words, any family of 𝑘-monotone functions is not
a exp 𝑂(𝑛 1/3 (𝑘 log 𝑛)2/3 ) , 1/3 -secure weak pseudorandom family.
The previous best distinguisher for 𝑘-monotone weak PRFs is the learning algorithm by
Blais et al. [5] which runs in exp 𝑂(𝑛 1/2 𝑘 log 𝑛) time. Our result improves this bound by an
Ω 𝑛 1/6 (𝑘 log 𝑛)1/3 factor in the exponent.
Theorem 1.3 implies that exponentially secure weak PRFs require log 𝑛 − 𝑂(log log 𝑛)
negations, which is optimal up to an additive 𝑂(log log 𝑛) 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 𝑂(𝑛 1/3 log2/3 𝑛) time. Therefore, unlike testing 1 negation (using 1-sided non-adaptive
tester) [13] and learning
√ 1 negation to high accuracy [5], distinguishing 1 negation does not
suffer from the exp( 𝑛) barrier.
It is natural to ask if we can leverage the distinguisher to a learning algorithm. Our second
result gives weak learning algorithms for 𝑘-monotone functions under the uniform distribution.
Theorem 1.4. 𝑘-monotone functions are weakly learnable in time exp 𝑂 𝑘 𝑛 log 𝑛 .
p
pOur result slightly improves the previous best weak learner due to Blais et al. [5], by a
log 𝑛 factor in the exponent.
Ω
We conjecture that both Theorem 1.3 and Theorem 1.4 are not tight. However, we believe
that any further improvement of our results, even for a single negation, requires completely
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 4
N EW D ISTINGUISHERS FOR N EGATION -L IMITED W EAK P SEUDORANDOM F UNCTIONS
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 𝑘-monotone functions on
low degree monomials, by bounding the total influence of 𝑘-monotone functions. Then they
apply the “Low-Degree Algorithm” established by Linial, Mansour, and Nisan [19] to learn
𝑘-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 Ω( 𝑛) levels [9], which will
require at least 𝑛 Ω( 𝑛) time by applying the “Low-Degree Algorithm”.
Our main technique is using Fourier analysis on slices [10, 25]. Although the Fourier
concentration on the Boolean cube cannot be improved, we show some “middle” slices of
𝑘-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 𝑘-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.
Organization of the paper. We begin with basic notation in Section 2, then present the structural
results for 𝑘-monotone functions in Section 3. In Sections 4 and 5, we present the distinguisher
and the weak learner, respectively.
2 Preliminaries
2.1 Notation, terminology: sets, strings, slices
In this paper, all the logarithms are base 2.
As usual, for 𝑛 ∈ ℕ we write [𝑛] = {1, 2, . . . , 𝑛}. The set of 𝑘-subsets (subsets of size 𝑘) of
[𝑛] is denoted [𝑛]
𝑘
.
We refer to the set {0, 1} 𝑛 as the 𝑛-dimensional Boolean hypercube; its elements are the
(0, 1)-strings of length 𝑛. For 0 ≤ 𝑟 ≤ 𝑛, the 𝑟-slice of the 𝑛-cube is the set
Õ
{(𝑥 1 , . . . , 𝑥 𝑛 ) ∈ {0, 1} 𝑛 : 𝑥 𝑖 = 𝑟} . (2.1)
𝑖
We identify subsets 𝐴 ⊆ [𝑛] with their indicator strings 𝑥 𝐴 = (𝑥 1 , . . . , 𝑥 𝑛 ) defined by
(
1 if 𝑖 ∈ 𝐴
𝑥𝑖 = (2.2)
0 if 𝑖 ∉ 𝐴 .
With this identification, the 𝑟-slice of the 𝑛-dimensional Boolean hypercube becomes identical
with the set [𝑛]
𝑟 .
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 5
Z HIHUAI C HEN , S IYAO G UO , Q IAN L I , C HENGYU L IN , AND X IAOMING S UN
2.2 Alternating number, negation complexity, 𝑘-monotone functions
For any two strings 𝑥, 𝑦 ∈ {0, 1} 𝑛 , we say 𝑥 ≺ 𝑦 (or 𝑦 𝑥) if 𝑥 ≠ 𝑦 and 𝑥 𝑖 ≤ 𝑦 𝑖 for all 𝑖 ∈ [𝑛].
A chain 𝑋 = (𝑥 1 , 𝑥 2 , . . . , 𝑥ℓ ) of length ℓ is an increasing sequence of strings in {0, 1} 𝑛 where
𝑥 𝑖 ≺ 𝑥 𝑖+1 for 𝑖 ∈ [ℓ − 1]. For a Boolean function 𝑓 : {0, 1} 𝑛 → {0, 1}, we define the alternating
number of 𝑓 on chain 𝑋 to be the number of value flips on this chain:
𝑎( 𝑓 , 𝑋) = {𝑖 ∈ [ℓ − 1] : 𝑓 (𝑥 𝑖 ) ≠ 𝑓 (𝑥 𝑖+1 )} . (2.3)
Let 𝒞 be the set of all chains on {0, 1} 𝑛 , the alternating number of 𝑓 is
𝑎( 𝑓 ) = max 𝑎( 𝑓 , 𝑋). (2.4)
𝑋∈𝒞
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 𝑓 to
the negation complexity N( 𝑓 ) – the minimum number of negation gates required in any Boolean
AND − OR circuits to compute 𝑓 .
Theorem 2.1 (Markov’s Theorem [20]). Let 𝑓 : {0, 1} 𝑛 → {0, 1} be a function which is not identically
0 with 𝑓 (0𝑛 ) = 0, then N( 𝑓 ) = dlog(𝑎( 𝑓 ) + 1)e − 1.
Blais et al. [5] showed decomposition for functions with low alternating number [5].
Theorem 2.2 (Theorem 1.1 in [5]). Let 𝑓 be a 𝑘-alternating function, then 𝑓 (𝑥) = ℎ(𝑚1 (𝑥), . . . , 𝑚 𝑘 (𝑥))
where 𝑚 𝑖 (𝑥) is monotone and h is the parity function or its negation. Conversely, any function of this
form is 𝑘-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 will focus on
the parity of few monotone functions.
Definition 2.3 (𝑘-monotone function). A function 𝑓 : {0, 1} 𝑛 → {0, 1} is said to be 𝑘-monotone,
if there exist 𝑘 monotone functions 𝑔1 , 𝑔2 , . . . , 𝑔 𝑘 such that 𝑓 = 𝑔1 ⊕ 𝑔2 ⊕ · · · ⊕ 𝑔 𝑘 .
2.3 Orthogonal basis for functions over a slice
[𝑛]
Given a subset of the 𝑟-slice, 𝐴 ⊆ , denote its density in this slice by 𝜇(𝐴), i. e., 𝜇(𝐴) = |𝐴|/ 𝑛𝑟 .
𝑟
Define its upper shadow as
( )
[𝑛]
𝜕+ 𝐴 := 𝑥 ∈ : 𝑥 𝑦 for some 𝑦 ∈ 𝐴 (2.5)
𝑟+1
and its lower shadow as
( )
[𝑛]
𝜕− 𝐴 := 𝑥 ∈ : 𝑥 ≺ 𝑦 for some 𝑦 ∈ 𝐴 . (2.6)
𝑟−1
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 6
N EW D ISTINGUISHERS FOR N EGATION -L IMITED W EAK P SEUDORANDOM F UNCTIONS
Filmus [10] and Srinivasan [25] independently introduced an orthogonal basis for functions
over a slice [𝑛]
𝑟 of the Boolean hypercube, which plays a central role in our proofs. Now we
describe the explicit formula provided by Filmus [10] (see also Section 9.2 in [11]).
Definition 2.4. For 𝑑 ≤ 𝑛/2, define a ℬ𝑛,𝑑 -sequence to be a sequence 𝐵 = 𝑏1 , 𝑏2 , · · · , 𝑏 𝑑 where (i)
all 𝑏1 , · · · , 𝑏 𝑑 belong to [𝑛], (ii) 𝑏1 < 𝑏2 < · · · < 𝑏 𝑑 , and (iii) 𝑏 𝑖 ≥ 2𝑖 for any 1 ≤ 𝑖 ≤ 𝑑. We will
also use ℬ𝑛,𝑑 to denote the set of all ℬ𝑛,𝑑 -sequences.
Given 𝐵 ∈ ℬ𝑛,𝑑 , define 𝒯 (𝐵) to be the set consisting of all sequences 𝐴 = 𝑎 1 , 𝑎2 , · · · , 𝑎 𝑑 of 𝑑
distinct elements of [𝑛] satisfying that (i) {𝑎 1 , · · · , 𝑎 𝑑 } ∩ {𝑏1 , · · · , 𝑏 𝑑 } = ∅ and (ii) 𝑎 𝑖 < 𝑏 𝑖 for all 𝑖.
Furthermore, we define
𝑑
Õ Ö
𝜒𝐵 = (𝑥 𝑎 𝑖 − 𝑥 𝑏 𝑖 ). (2.7)
𝐴∈𝒯 (𝐵) 𝑖=1
Theorem 2.5 (Theorem 15 in [10]). Let 𝑟 ≤ 𝑛/2 be an integer, the set {𝜒𝐵 : 𝐵 ∈ ℬ𝑛,𝑑 for some 𝑑 ≤ 𝑟}
is an orthogonal basis for the vector space of functions over the slice [𝑛]
𝑟 . The Young-Fourier expansion
[𝑛]
of 𝑓 : 𝑟 → ℝ is the unique representation
Õ
𝑓 = 𝑓ˆ(𝐵)𝜒𝐵 , (2.8)
𝐵∈ℬ𝑛,𝑑 , 𝑑≤𝑟
h 𝑓 ,𝜒 i
where 𝑓ˆ(𝐵) = k𝜒 k𝐵2 . Here h 𝑓 , 𝑔i := 𝔼𝑥∼𝑈 [ 𝑓 (𝑥)𝑔(𝑥)]. In addition for 𝐵 ∈ ℬ𝑛,𝑑 ,
𝐵 2
𝑑 𝑑
· 2𝑑 𝑟 (𝑛−𝑟)
Î𝑑
1. k𝜒𝐵 k 22 = (𝑏 𝑖 −2(𝑖−1))(𝑏 𝑖 −2(𝑖−1)−1)
𝑖=1 2 𝑛 2𝑑 = 𝑛 𝑂(𝑑) . In particular, if 𝑟 ≥ 𝑛4 and 𝑑 = 𝑜(𝑛),
then k𝜒𝐵 k 22 = 2−𝑂(𝑑) . Here, 𝑟 𝑑 = 𝑑−1 𝑖=0 (𝑟 − 𝑖).
Î
𝑂(𝑑) .
𝐴∈𝒯 (𝐵) k𝜒𝐴,𝐵 k ∞ = 𝑛
Í
2. k𝜒𝐵 k ∞ ≤
By Boolean duality, we can extend the above Young-Fourier expansion to where 𝑟 > 𝑛/2
naturally. This can be done by replacing the basis {𝜒𝐵 (𝑥)} by {𝜒𝐵¯ (𝑥) := 𝜒𝐵 ( 𝑥)}
¯ where 𝑥¯ is
obtained by flipping all bits of 𝑥.
Corollary 2.6. Let 𝑟 > 𝑛/2 be an integer, the set {𝜒𝐵¯ (𝑥) : 𝐵 ∈ ℬ𝑛,𝑑 for some 𝑑 ≤ 𝑛 − 𝑟} is an orthogonal
basis for the vector space of functions over the slice [𝑛]
𝑟 . The Young-Fourier expansion of 𝑓
: [𝑛]
𝑟 →ℝ
is the unique representation
Õ
𝑓 = 𝑓ˆ(𝐵)𝜒 ¯ , 𝐵 (2.9)
𝐵∈ℬ𝑛,𝑑 , 𝑑≤𝑛−𝑟
h 𝑓 ,𝜒 i
where 𝑓ˆ(𝐵) = k𝜒 k𝐵¯2 . In addition, we have k𝜒𝐵¯ k 22 = k𝜒𝐵 k 22 and k𝜒𝐵¯ k ∞ = k𝜒𝐵 k ∞ .
𝐵¯ 2
Like for functions over the Boolean hypercube, we can define the total weight on level 𝑑:
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 7
Z HIHUAI C HEN , S IYAO G UO , Q IAN L I , C HENGYU L IN , AND X IAOMING S UN
Definition 2.7. Let 𝑓 : [𝑛]
𝑟 → ℝ, for any 𝑟 ≤ 𝑛, define
Õ
W𝑑 ( 𝑓 ) = 𝑓ˆ(𝐵)2 k𝜒𝐵 k 22 , (2.10)
𝐵∈ℬ𝑛,𝑑
and denote W>𝑑 ( 𝑓 ) = 𝑑 and W≤𝑑 ( 𝑓 ) = Í 𝑑
Í
𝑑0 >𝑑 W 𝑑0 ≤𝑑 W .
Definition 2.8. Let 𝑓 : [𝑛]
𝑟 → {±1}. For 𝑖, 𝑗 ∈ [𝑛], define the influence of 𝑓 on the pair (𝑖, 𝑗) as
I𝑖𝑗 [ 𝑓 ] = 2 Pr[ 𝑓 (𝑥 (𝑖,𝑗) ) ≠ 𝑓 (𝑥)]. (2.11)
Here 𝑥 (𝑖,𝑗) is obtained by switching 𝑥 𝑖 and 𝑥 𝑗 . The total influence of 𝑓 is
1 Õ
I[ 𝑓 ] = I𝑖𝑗 [ 𝑓 ]. (2.12)
𝑛
1≤𝑖<𝑗≤𝑛
Lemma 2.9 (Proposition 3.1 in [22]). Let 𝑓 : [𝑛]
𝑟 → {±1} and 𝐴 = {𝑥 ∈
[𝑛]
: 𝑓 (𝑥) = −1}, then
𝑟
𝑛 1
min{𝜇(𝜕+ 𝐴), 𝜇(𝜕− 𝐴)} ≥ 𝜇(𝐴) + · I[ 𝑓 ] ≥ 𝜇(𝐴) + I[ 𝑓 ]. (2.13)
4𝑟(𝑛 − 𝑟) 𝑛
Theorem 2.10 (Lemma 24 in [10]). Let 𝑓 : [𝑛]
𝑟 → {±1}. Then
Õ 𝑑(𝑛 + 1 − 𝑑) Õ 𝑑(𝑛 + 1 − 𝑑) ˆ 2
I[ 𝑓 ] = · W𝑑 = · 𝑓 (𝐵) k𝜒𝐵 k 22 . (2.14)
𝑛 𝑛
𝑑≤min(𝑟,𝑛−𝑟) 𝐵∈ℬ𝑛,𝑑 ,𝑑≤min(𝑟,𝑛−𝑟)
In addition, according to Parseval’s identity,
Õ Õ
W𝑑 = 𝑓ˆ(𝐵)2 k𝜒𝐵 k 22 = k 𝑓 k 22 = 1. (2.15)
𝑑 𝐵∈ℬ𝑛,𝑑 ,𝑑≤min(𝑟,𝑛−𝑟)
2.4 Basic inequalities
Finally, we will make use of the Hoeffding bound.
Í𝑛
Theorem 2.11 (Hoeffding Bound, Theorem 2 in [17]). Let 𝑋 = 𝑖=1 𝑋𝑖 , where 𝑋𝑖 ∈ [𝑎 𝑖 , 𝑏 𝑖 ] are
independent random variables. Then for any 𝜃 > 0,
!
2𝜃2
Pr(|𝑋 − 𝔼(𝑋)| ≥ 𝜃) ≤ 2 exp − . (2.16)
Σ𝑖 (𝑏 𝑖 − 𝑎 𝑖 )2
Corollary 2.12. Let 𝑋 be a random variable with distribution 𝒟 whose range is [𝑙, 𝑢]. Let 𝑋1 , . . . , 𝑋𝑚
be its independent samples. Then w.p. ≥ 1 − 𝛿, for any 𝜖 > 0,
𝑚
1 Õ
𝑋𝑖 − 𝔼(𝑋) ≤ 𝜖 (2.17)
𝑚
𝑖=1
as long as 𝑚 ≥ (𝑢 − 𝑙)2 log(2/𝛿)/(2𝜖 2 ).
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 8
N EW D ISTINGUISHERS FOR N EGATION -L IMITED W EAK P SEUDORANDOM F UNCTIONS
The following fact will also be used.
𝑛
Proposition 2.13. For 𝑡 = 𝑜(𝑛) we have 𝑛/2−𝑡/2 /2𝑛 = √1𝑛 · 2−Θ(𝑡 /𝑛) .
2
Proof. By Stirling’s approximation,
𝑛 𝑛 𝑛/2 − 𝑡/2
r
log = log(1 + 𝑜(1)) + log +𝑛·𝐻 , (2.18)
𝑛/2 − 𝑡/2 2𝜋(𝑛/2 − 𝑡/2)(𝑛/2 + 𝑡/2) 𝑛
where 𝐻(𝑝) = −𝑝 log 𝑝 − (1 − 𝑝) log(1 − 𝑝) is the binary entropy function. As 𝑡/2𝑛 = 𝑜(1), by the
Taylor expansion of the entropy function around 1/2, we have
𝑡 1 + 𝑜(1) 𝑡
2
1
𝐻 − =1− . (2.19)
2 2𝑛 2 ln 2 𝑛
The conclusion follows immediately.
3 Concentration property of 𝑘-monotone functions
In the rest of this paper, for a function 𝑓 : {0, 1} 𝑛 → {0, 1}, we convert the range to {±1}. The
mapping from {0, 1} to {−1, 1} is given by 1 − 2𝑏, sending 0 to 1 and 1 to −1. So a function
𝑓 : {0, 1} 𝑛 → {±1} is said to be 𝑘-monotone if (1 − 𝑓 )/2 is 𝑘-monotone.
In this section, we show that some “middle” slice of a 𝑘-monotone function has Fourier
concentration. For functions 𝑓 : {0, 1} 𝑛 → {±1}, let 𝑓 | 𝑟 be the subfunction of 𝑓 restricted to [𝑛]
𝑟
and 𝜇( 𝑓 | 𝑟 ) := 𝜇( 𝑓 | −1
𝑟 (−1)).
Definition 3.1 ((𝑡, 𝑑, 𝜖)-concentration). We say 𝑓 : {0, 1} 𝑛 → {±1} is (𝑡, 𝑑, 𝜖)-concentrated if the
following holds: for some 𝑟 such that 𝑛/2 − 𝑡/2 ≤ 𝑟 ≤ 𝑛/2 + 𝑡/2,
Õ
W>𝑑 ( 𝑓 | 𝑟 ) = 𝑓 | 𝑟 (𝐵)2 k𝜒𝐵 k 2 < 𝜖.
c
2 (3.1)
𝐵∈ℬ𝑛,𝑑0 :𝑑0 >𝑑
Intuitively, 𝑓 has low-degree Fourier concentration on at least one of the middle slices.
Lemma 3.2. Let 𝑓 : {0, 1} 𝑛 → {±1} be a 𝑘-monotone function. For any 1 < 𝑡 ≤ 𝑛 and any 𝑑, 𝜖 such
that 𝑑𝜖 ≥ 2𝑘𝑛/𝑡, we have that 𝑓 is (𝑡, 𝑑, 𝜖)-concentrated.
Lemma 3.2 follows from an upper bound on the sum of total influences on slices.
Í𝑛−1
Proposition 3.3. Let 𝑓 : {0, 1} 𝑛 → {±1} be a 𝑘-monotone function. Then 𝑟=0 I[ 𝑓 | 𝑟 ] ≤ 𝑘𝑛.
We first prove Lemma 3.2 using Proposition 3.3.
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 9
Z HIHUAI C HEN , S IYAO G UO , Q IAN L I , C HENGYU L IN , AND X IAOMING S UN
Proof of Lemma 3.2. By contradiction, we assume that W>𝑑 ( 𝑓 | 𝑟 ) > 𝜖 ≥ 2𝑘𝑛
𝑑𝑡 for any 𝑛/2 − 𝑡/2 ≤
Í b𝑛/2+𝑡/2c
𝑟 ≤ 𝑛/2 + 𝑡/2. According to Proposition 3.3, we have 𝑟=d𝑛/2−𝑡/2e I[ 𝑓 | 𝑟 ] ≤ 𝑘𝑛. By averaging, let
𝑛/2 − 𝑡/2 ≤ 𝑟 ≤ 𝑛/2 + 𝑡/2 be such that I[ 𝑓 | 𝑟 ] ≤ 𝑘𝑛/𝑡. By Theorem 2.10, we can deduce that,
𝑘𝑛 Õ 𝑑0(𝑛 + 1 − 𝑑0)
· W𝑑 ( 𝑓 | 𝑟 )
0
≥ I[ 𝑓 | 𝑟 ] = (3.2)
𝑡 𝑛
0 𝑑 ≤min(𝑟,𝑛−𝑟)
Õ 𝑑0(𝑛 + 1 − 𝑑0)
· W𝑑 ( 𝑓 | 𝑟 )
0
≥ (3.3)
𝑛
𝑑<𝑑0 ≤min(𝑟,𝑛−𝑟)
𝑑(𝑛 + 1 − 𝑑) Õ
W𝑑 ( 𝑓 | 𝑟 )
0
≥ · (3.4)
𝑛
𝑑<𝑑0 ≤min(𝑟,𝑛−𝑟)
𝑑 𝑑 2𝑘𝑛 𝑘𝑛
> ·𝜖≥ · ≥ , (3.5)
2 2 𝑑𝑡 𝑡
a contradiction.
Now we prove Proposition 3.3.
Proof of Proposition 3.3. Suppose 𝑓 is the parity of ℎ 1 , · · · , ℎ 𝑘 where each ℎ 𝑖 is monotone. For any
𝑟, when we switch 𝑥 𝑖 and 𝑥 𝑗 , 𝑓 | 𝑟 (𝑥) changes only if at least one ℎ 𝑖 | 𝑟 (𝑥) changes for 𝑖 = 1, 2, . . . , 𝑘.
Thus, combining with the union bound, we have
𝑘
Õ
I[ 𝑓 | 𝑟 ] ≤ I[ℎ 𝑖 | 𝑟 ]. (3.6)
𝑖=1
Since ℎ 𝑖 is monotone, the upper shadow of ℎ 𝑖 | −1 𝑟 (−1) is a subset of ℎ 𝑖 | 𝑟+1 (−1). Then according
−1
to Lemma 2.9, we have
1
𝜇(ℎ 𝑖 | 𝑟+1 ) ≥ 𝜇(ℎ 𝑖 | 𝑟 ) + 𝐼(ℎ 𝑖 | 𝑟 ), (3.7)
𝑛
which implies
𝑛−1
1Õ
I[ℎ 𝑖 | 𝑟 ] ≤ 𝜇(ℎ 𝑖 | 𝑛 ) − 𝜇(ℎ 𝑖 | 0 ) ≤ 1. (3.8)
𝑛
𝑟=0
Equation (3.6) and Equation (3.8) imply the desired conclusion.
4 Distinguishers for 𝑘-monotone functions
In this section, we prove the following theorem.
family of 𝑘-monotone
Theorem 1.3. Any functions can be distinguished from uniformly random
functions in exp 𝑂(𝑛 1/3 (𝑘 log 𝑛)2/3 ) time. In other words, any family of 𝑘-monotone functions is not
a exp 𝑂(𝑛 1/3 (𝑘 log 𝑛)2/3 ) , 1/3 -secure weak pseudorandom family.
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 10
N EW D ISTINGUISHERS FOR N EGATION -L IMITED W EAK P SEUDORANDOM F UNCTIONS
Algorithm 1: A Distinguisher for (𝑡, 𝑑, 1/2)-Concentrated Functions
1 Let 𝐶 be a large enough constant;
𝑛 𝑡 𝑛 𝑡
2 for 𝑟 ← d 2 − 2 e to b 2 + 2 c do
3 𝑆 ← 0;
4 for 𝐵 ∈ ℬ𝑛,𝑑0 with 𝑑0 ≤ 𝑑 do
5 if 𝑟 ≤ 𝑛/2 then
6 Estimate h 𝑓 | 𝑟 , 𝜒𝐵 i with accuracy 𝑛 −𝐶·𝑑 ;
7 𝑆←𝑆+ c
𝑓 | 𝑟 (𝐵)2 k𝜒𝐵 k 22 ;
𝑓 | 𝑟 (𝐵)2 k𝜒𝐵 k 22 = h 𝑓 | 𝑟 , 𝜒𝐵 i 2 /k𝜒𝐵 k 22
// c
8 else
9 Estimate h 𝑓 | 𝑟 , 𝜒𝐵¯ i with accuracy 𝑛 −𝐶·𝑑 ;
10 𝑆←𝑆+ c ¯ 2 k𝜒 ¯ k 2 ;
𝑓 | 𝑟 (𝐵) 𝐵 2
𝑓 | 𝑟 (𝐵)2 k𝜒 ¯ k 2 = h 𝑓 | 𝑟 , 𝜒 ¯ i 2 /k𝜒 ¯ k 2
// c 𝐵 2 𝐵 𝐵 2
11 if 𝑆 ≥ 3/8 then
12 Return True;
13 Return False;
We prove this theorem by giving a distinguisher for (𝑡, 𝑑, 1/2)-concentrated functions.
Proposition 4.1. For 𝑡 ≤ 𝑛/4 and 𝑑 = 𝑜(𝑛/log 𝑛), any family of (𝑡, 𝑑, 1/2)-concentrated functions can
be distinguished from uniform random functions in 2𝑂(𝑑 log 𝑛+𝑡 /𝑛) time.
2
𝑘 𝑛
By Lemma 3.2, every 𝑘-monotone function is (𝑘𝑛 2 log 𝑛)1/3 , 4 log , 1/2 -concentrated,
2 1/3
𝑛
then Theorem 1.3 follows. Now we prove the proposition.
Proof. The distinguisher is given in Algorithm 1. We will show that
• (Soundness) It accepts a uniform random function w.p. 𝑜(1);
• (Completeness) It accepts any (𝑡, 𝑑, 1/2)-concentrated function w.p. 1 − 𝑜(1);
• (Complexity) Its sample/time complexity is 2𝑂(𝑑 log 𝑛+𝑡 /𝑛) .
2
Soundness. Let 𝑓 be a uniform random function. We claim that for each 𝑛2 − 2𝑡 ≤ 𝑟 ≤ 𝑛2 + 2𝑡 ,
the variable 𝑆 in Line 11 is at most 1/4 w.p. 1 − 𝑜( 𝑛1 ), which concludes the soundness by the
union bound.
Fix such an 𝑟. W.l.o.g., we assume that 𝑟 ≤ 𝑛/2. For any 𝐵 ∈ ℬ𝑛,𝑑0 where 𝑑0 ≤ 𝑑, it is easily
seen that 𝔼 𝑓 h 𝑓 | 𝑟 , 𝜒𝐵 i = 0, then by the Hoeffding bound,
! 𝑛/4−𝑜(𝑛) !
𝑛
4
Pr h 𝑓 | 𝑟 , 𝜒𝐵 i ≥ 𝜃 ≤ 2 exp −2𝜃 2 ,
k𝜒𝐵 k 22 ≤ 2 exp −𝜃 2 (4.1)
𝑓 𝑟 3
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 11
Z HIHUAI C HEN , S IYAO G UO , Q IAN L I , C HENGYU L IN , AND X IAOMING S UN
where the last inequality is due to that 𝑛𝑟 ≥ ( 𝑛𝑟 )𝑟 ≥ ( 43 )𝑛/4 and k𝜒𝐵 k 22 = 2𝑂(𝑑 log 𝑛) = ( 34 )𝑜(𝑛) . In
𝑛/10
particular, by letting 𝜃 = 3
4 and using the union bound, we have that with probability at
𝑛/4−𝑜(𝑛)
least 1 − 𝑛 𝑂(𝑑) · exp −𝜃2 4
3 = 1 − 𝑜( 𝑛1 ), h 𝑓 | 𝑟 , 𝜒𝐵 i < 𝜃 for every 𝐵 ∈ ℬ𝑛,𝑑0 where 𝑑0 ≤ 𝑑.
Thus, w.p. 1 − 𝑜( 𝑛1 ),
Õ Õ h 𝑓 | 𝑟 , 𝜒𝐵 i 2 Õ 𝜃2 1
W≤𝑑 [ 𝑓 | 𝑟 ] = 𝑓 | 𝑟 (𝐵)2 k𝜒𝐵 k 2 =
c
2 ≤ ≤ , (4.2)
𝐵∈ℬ𝑛,𝑑 0 ,𝑑0 ≤𝑑 𝐵∈ℬ𝑛,𝑑 0 ,𝑑0 ≤𝑑
k𝜒𝐵 k 22 𝐵∈ℬ𝑛,𝑑0 ,𝑑0 ≤𝑑
k𝜒𝐵 k 22 8
where the last inequality holds for sufficiently large 𝑛. Finally, 𝑆 is an estimate of W≤𝑑 [ 𝑓 | 𝑟 ] with
additive error 𝑛 −Ω(𝑑) .
Completeness. Let 𝑓 be a (𝑡, 𝑑, 1/2)-concentrated function. By definition, there is some 𝑟
such that 𝑛/2 − 𝑡/2 ≤ 𝑟 ≤ 𝑛/2 + 𝑡/2 and 𝑊 ≤𝑑 [ 𝑓 | 𝑟 ] > 1/2. As 𝑆 is an estimate of W≤𝑑 [ 𝑓 | 𝑟 ] with
additive error 𝑛 −Ω(𝑑) , we conclude that Algorithm 1 accepts 𝑓 with high probability.
Complexity. The loop in Line 2 is repeated at most 𝑡 times. In Line 4, the number of strings
𝐵 ∈ ℬ𝑛,𝑑0 with 𝑑0 ≤ 𝑑 we enumerated is at most 𝑛 𝑂(𝑑) . Furthermore, for each 𝑛/2 − 𝑡/2 ≤ 𝑟 ≤
𝑛/2 + 𝑡/2 and each 𝐵 ∈ ℬ𝑛,𝑑0 with 𝑑0 ≤ 𝑑, according to the Hoeffding bound, 𝑛 𝑂(𝑑) uniform
random samples on the slice [𝑛] h 𝑓 | 𝑟 , 𝜒𝐵 i with accuracy 𝑛 −𝐶·𝑑 . In
𝑟 are sufficient to estimate
𝑛 𝑛
addition, a random uniform sample is from the slice [𝑛]
𝑟 with probability 𝑟 /2 , which is
√1 · 2−𝑂(𝑡 /𝑛) according to Proposition 2.13. Thus, the total number of random samples used is
2
𝑛
at most 𝑡 · 𝑛 𝑂(𝑑) · 𝑛 𝑂(𝑑) · 2𝑂(𝑡 /𝑛) = 2𝑂(𝑑 log 𝑛+𝑡 /𝑛) .
2 2
Besides, the function 𝜒𝐵 = 𝐴∈𝒯 (𝐵) 𝜒𝐴,𝐵 can be computed by enumerating all 𝑛 𝑂(𝑑) strings 𝐴
Í
in 𝒯 (𝐵). Thus, the time complexity is also 2𝑂(𝑑 log 𝑛+𝑡 /𝑛) .
2
5 Weak learners for 𝑘-monotone functions
In this section, we prove the following theorem.
Theorem 1.4. 𝑘-monotone functions are weakly learnable in time exp 𝑂 𝑘 𝑛 log 𝑛 .
p
We prove Theorem 1.4 by giving a weak learner for (𝑡, 𝑑, 1/2)-concentrated functions. By
q
𝑛
Lemma 3.2, 𝑘-monotone functions are 𝑛 log 𝑛, 4𝑘 log 𝑛 , 1/2 -concentrated, then Theorem 1.4
p
follows.
Proposition 5.1. For 𝑡 = 𝑂( 𝑛 log 𝑛) and 𝑑 = 𝑜(𝑛/log 𝑛), Algorithm 2 weakly learns (𝑡, 𝑑, 1/2)-
p
concentrated functions in 2𝑂(𝑑 log 𝑛+𝑡 /𝑛) time.
2
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 12
N EW D ISTINGUISHERS FOR N EGATION -L IMITED W EAK P SEUDORANDOM F UNCTIONS
Algorithm 2: A weak learner for (𝑡, 𝑑, 1/2)-concentrated functions
1 Let 𝐶 be a large enough constant;
𝑛 𝑡 𝑛 𝑡
2 for 𝑟 ← 2 − 2 to 2 + 2 do
3 𝑆 ← 0;
4 𝑝 ← 1;
5 for 𝐵 ∈ ℬ𝑛,𝑑0 with 𝑑0 ≤ 𝑑 do
6 if 𝑟 ≤ 𝑛/2 then
7 Estimate h 𝑓 | 𝑟 , 𝜒𝐵 i with accuracy 𝑛 −𝐶·𝑑 ;
8 𝑆←𝑆+ c
𝑓 | 𝑟 (𝐵)2 k𝜒𝐵 k 22 ;
9 else
10 Estimate h 𝑓 | 𝑟 , 𝜒𝐵¯ i with accuracy 𝑛 −𝐶·𝑑 ;
11 𝑆←𝑆+ c
𝑓 | 𝑟 (𝐵)2 k𝜒𝐵¯ k 22 ;
12 if 𝑆 ≥ 3/8 then
13 if 𝑟 ≤ 𝑛/2 then
𝑔(𝑥) ← 𝐵∈ℬ𝑛,𝑑0 :𝑑0 ≤𝑑 c
𝑓 | 𝑟 (𝐵)𝜒𝐵 (𝑥);
Í
14
15 else
𝑔(𝑥) ← 𝐵∈ℬ𝑛,𝑑0 :𝑑0 ≤𝑑 c
𝑓 | 𝑟 (𝐵)𝜒𝐵¯ (𝑥);
Í
16
√
17 while 𝑝 > 3/4 do
18 Pick 𝜃 ∈ [−1, 1] uniformly at random;
19 Estimate 𝑝 ← Pr[ 𝑓 | 𝑟 ≠ sign(𝑔 − 𝜃)];
20 Estimate 𝜇≠𝑟 ← 𝔼𝑥 [ 𝑓 (𝑥) | |𝑥| ≠ 𝑟];
(
sign(𝑔(𝑥) − 𝜃) if |𝑥| = 𝑟;
21 Return ℎ(𝑥) =
sign(𝜇≠𝑟 ) if |𝑥| ≠ 𝑟.
22 Return ℎ(𝑥) ≡ 0.
To learn (𝑡, 𝑑, 1/2)-concentrated functions 𝑓 , Algorithm 2 tries to find out the slice [𝑛]
𝑟
on which 𝑓 | 𝑟 is concentrated, and then figures out a function 𝑔 : [𝑛]
𝑟 → ℝ which is very
close to 𝑓 | 𝑟 . To convert the approximated function 𝑔 to a Boolean-valued function, we can
utilize Claim 5.2 similar to Exercise 3.34 in [21]. p For the rest of the slices, the learner just
outputs the most frequent value. Since 𝑡 = 𝑂( 𝑛 log 𝑛), each slice in [𝑛/2 − 𝑡/2, 𝑛/2 + 𝑡/2]
is at least a √1𝑛 · 2−𝑂(𝑡 /𝑛) = 1/poly(𝑛) fraction according to Proposition 2.13. Hence we get a
2
(1/2 − 1/poly(𝑛))-close function ℎ.
Proof of Proposition 5.1. We first show that Algorithm 2 weakly learns (𝑡, 𝑑, 1/2)-concentrated
functions. Let 𝑓 be a (𝑡, 𝑑, 1/2)-concentrated function. For each 𝑛/2 − 𝑡/2 ≤ 𝑟 ≤ 𝑛/2 + 𝑡/2, the
variable 𝑆 in Line 12 is an estimate of W≤𝑑 [ 𝑓 | 𝑟 ] with additive error 𝑛 −Ω(𝑑) . Then for some 𝑟, the
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 13
Z HIHUAI C HEN , S IYAO G UO , Q IAN L I , C HENGYU L IN , AND X IAOMING S UN
condition 𝑆 ≥ 3/8 in Line 12 holds, and Algorithm 2 executes Lines 13-21. For the function 𝑔
obtained in Line 14 or Line 16, and sufficiently large 𝑛,
s Õ p √
|| 𝑓 | 𝑟 − 𝑔|| 1 ≤ || 𝑓 | 𝑟 − 𝑔|| 2 = 𝑓 | 𝑟 (𝐵) − 𝑔(𝐵))
(c ˆ 2 k𝜒 k 2 + 𝑊 >𝑑 [ 𝑓 | ] ≤ 𝑜(1) + 5/8 ≤
𝐵 2 𝑟 3/2.
𝐵∈ℬ𝑛,𝑑0 ,𝑑0 ≤𝑑
To convert 𝑔 to a Boolean-valued function, we utilize the following claim.
Claim 5.2. Suppose 𝑓 : [𝑛]
𝑟 → {−1, 1} and 𝑔
: [𝑛]
𝑟 → ℝ. Pick 𝜃 ∈ [−1, 1] uniformly at random and
define 𝑔 = sign 𝑔(𝑥) − 𝜃 , we have 𝔼𝜃 Pr𝑥 𝑓 (𝑥) ≠ 𝑔 0(𝑥) ≤ k 𝑓 − 𝑔 k 1 /2.
0
Proof. By rewriting the last formula and swapping the expectation operators, we have
h i h i
0
𝔼 Pr 𝑓 (𝑥) ≠ 𝑔 (𝑥) = 𝔼 𝔼 1 𝑓 (𝑥)≠𝑔0(𝑥) = 𝔼 𝔼 1 𝑓 (𝑥)≠𝑔0(𝑥) = 𝔼 Pr 𝑓 (𝑥) ≠ sign(𝑔(𝑥) − 𝜃)
𝜃 𝑥 𝜃 𝑥 𝑥 𝜃 𝑥 𝜃
| 𝑓 (𝑥) − 𝑔(𝑥)| k 𝑓 − 𝑔k 1
≤𝔼 = .
𝑥 2 2
√
Thus, for a random 𝜃 ∈ [−1, 1], Pr 𝑓 | 𝑟 (𝑥) ≠ sign(𝑔(𝑥) − 𝜃) ≤ 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 𝜃 such that Pr 𝑓 | 𝑟 (𝑥) ≠ sign(𝑔(𝑥) − 𝜃 ) ≤ 3/4. Finally, we have
Pr[ℎ(𝑥) ≠ 𝑓 (𝑥)] (5.1)
★
= Pr[|𝑥| ≠ 𝑟] Pr[ 𝑓 (𝑥) ≠ sign(𝜇≠𝑟 ) | |𝑥| ≠ 𝑟] + Pr[|𝑥| = 𝑟] Pr 𝑓 | 𝑟 (𝑥) ≠ sign(𝑔(𝑥) − 𝜃 )
(5.2)
𝑛 𝑛 √ 𝑛 √
! !
𝑟 1 𝑟 3 1 𝑟 3 1
≤ 1− 𝑛 · + 𝑛 · = + 𝑛 · − (5.3)
2 2 2 4 2 2 4 2
√ !
1 1 3 1 1 1
· √ · 2−𝑂(𝑡 /𝑛) = − ,
2
= − − (5.4)
2 2 4 𝑛 2 poly(𝑛)
where the penultimate equality
p is according to Proposition 2.13 and the last equality is due to
the assumption that 𝑡 = 𝑂( 𝑛 log 𝑛).
What remains is to show that Algorithm 2 terminates in 2𝑂(𝑑 log 𝑛+𝑡 /𝑛) time. First, as shown
2
in the analysis of Algorithm 1, for each 𝑛/2 − 𝑡/2 ≤ 𝑟 ≤ 𝑛/2 + 𝑡/2, it costs 2𝑂(𝑑 log 𝑛+𝑡 /𝑛) time
2
to execute Lines 5-11. For some 𝑟, 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𝑂(𝑑 log 𝑛+𝑡 /𝑛) time to execute
2
Lines 13-21. Therefore the total time complexity is 𝑡 · 2𝑂(𝑑 log 𝑛+𝑡 /𝑛) = 2𝑂(𝑑 log 𝑛+𝑡 /𝑛) .
2 2
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
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 14
N EW D ISTINGUISHERS FOR N EGATION -L IMITED W EAK P SEUDORANDOM F UNCTIONS
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 a very 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𝑂( 𝑛) . 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 𝑘-monotone functions on low levels. It is a basic fact [21] that every
monotone function 𝑓 : {0, 1} 𝑛 → {−1, 1} has a large Fourier coefficient on the first two levels.
Does a similar statement hold for 𝑘-monotone functions? We are particularly interested in
and focus on the case when 𝑘 = 𝑜(𝑛). On one hand, there exist 𝑘-monotone functions 𝑓 (e.g.,
𝑓 = 𝑥 1 ⊕ · · · ⊕ 𝑥 𝑘 ) such that max|𝑆|≤𝑘−1 | 𝑓ˆ(𝑆)| = 0. Second, the minimum max|𝑆|≤𝑘 | 𝑓ˆ(𝑆)| among
𝑘 𝑂(𝑘)
𝑘
all 𝑘-monotone functions that we are aware of so far is about ln(𝑛/𝑘)
𝑛/𝑘
= 𝑛 , which is
achieved by the parity of 𝑘 Tribes𝑛/𝑘 functions on disjoint variables. So we are curious about the
following conjectures.
Conjecture 6.1 (Rocco Servedio, 2014). For 𝑘 = 𝑜(𝑛) and any 𝑘-monotone function 𝑓 : {0, 1} 𝑛 →
𝑂(𝑘)
𝑘
{−1, 1}, there exists a set 𝑆 ⊆ [𝑛] of size at most 𝑘 such that | 𝑓ˆ(𝑆)| = 𝑛 .
If Conjecture 6.1 is true, then applying “Low-Degree Algorithm” on the Boolean cube [19],
we can distinguish 𝑘-monotone functions from uniformly random functions in (𝑛/𝑘)𝑂(𝑘) time.
When 𝑘 is constant, it also leads to a polynomial time weak learner.
We conjecture
(𝑛/𝑘)Θ(𝑘) is the
correct bound of distinguishers, specifically, there exists a (𝑛/𝑘)Θ(𝑘) , 1/3 -secure 𝑘-monotone
weak pseudorandom family.
In fact, our first attempt to distinguish 𝑘-monotone functions is to prove Conjecture 6.1. So
far, even the following much weaker conjecture remains open.
Conjecture 6.2 (Rocco Servedio, 2014). Let 𝑓 : {0, 1} 𝑛 → {−1, 1} be a 2-monotone function. There
√
exists a set 𝑆 ⊆ [𝑛] of size 𝑜( 𝑛) such that | 𝑓ˆ(𝑆)| > 0.
√
We note that it is easy to derive that there exists a set 𝑆 ⊆ [𝑛] of size 𝑂( 𝑛) such that
√
| 𝑓ˆ(𝑆)| > 0 by the 𝑂( 𝑛) total influence upper bound of 2-monotone function shown by Blais et
al [5]. We are not aware of other relevant results or implications.
Acknowledgments. We sincerely thank the ToC editors and the anonymous ToC 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
Conjecture 6.2 and an early version of Conjecture 6.1.
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 15
Z HIHUAI C HEN , S IYAO G UO , Q IAN L I , C HENGYU L IN , AND X IAOMING S UN
References
[1] Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen: Candidate
weak pseudorandom functions in 𝐴𝐶 0 ◦ 𝑀𝑂𝐷2 . In Proc. 5th Innovations in Theoret. Comp.
Sci. Conf. (ITCS’14), pp. 251–260. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2014.
[doi:10.1145/2554797.2554821] 2
[2] Noga Alon and Ravi B Boppana: The monotone circuit complexity of Boolean functions.
Combinatorica, 7(1):1–22, 1987. [doi:10.1007/BF02579196] 2
[3] Alexander E Andreev: A method for obtaining efficient lower bounds for mono-
tone complexity. Algebra and Logic, 26(1):1–18, 1987. Preliminary version in Doklady
282, 1985, pp.1033-1037. Original article in Algebra i Logika 26(1) 3–26, 1987 (Russian).
[doi:10.1007/BF01978380] 2
[4] Christer Berg and Staffan Ulfberg: Symmetric approximation arguments for
monotone lower bounds without sunflowers. Comput. Complexity, 8(1):1–20, 1999.
[doi:10.1007/s000370050017] 2
[5] Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang
Tan: Learning circuits with few negations. In Proc. 18th Internat. Workshop on Approximation
Algorithms for Combinat. Opt. Probl. (APPROX’15), pp. 512–527. Schloss Dagstuhl–Leibniz-
Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.512] 3, 4, 5,
6, 15
[6] Avrim Blum, Carl Burch, and John Langford: On learning monotone Boolean functions.
In Proc. 39th FOCS, pp. 408–415. IEEE Comp. Soc., 1998. [doi:10.1109/SFCS.1998.743491] 3
[7] Andrej Bogdanov and Alon Rosen: Pseudorandom functions: Three decades later. In
Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography, pp. 79–158. Springer,
2017. [doi:10.1007/978-3-319-57048-8_3] 2
[8] Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer:
Testing 𝑘-monotonicity: The rise and fall of Boolean functions. Theory of Computing,
15(1):1–55, 2019. Preliminary version in ITCS’17. [doi:10.4086/toc.2019.v015a001] 3
[9] Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, and Karl Wimmer:
Approximate resilience, monotonicity, and the complexity of agnostic learning. In Proc.
26th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’15), pp. 498–511. SIAM, 2015.
[doi:10.1137/1.9781611973730.34] 5
[10] Yuval Filmus: An orthogonal basis for functions over a slice of the Boolean hypercube.
Electr. J. Combinat., 23(1):P1.23, 2016. [doi:10.37236/4567] 5, 7, 8
[11] Yuval Filmus and Elchanan Mossel: Harmonicity and invariance on slices of the Boolean
cube. In Proc. 31st Comput. Complexity Conf. (CCC’16), pp. 16:1–13. Schloss Dagstuhl–Leibniz-
Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.16] 7
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 16
N EW D ISTINGUISHERS FOR N EGATION -L IMITED W EAK P SEUDORANDOM F UNCTIONS
[12] Oded Goldreich, Shafi Goldwasser, and Silvio Micali: How to construct random functions.
J. ACM, 33(4):792–807, 1986. [doi:10.1145/6490.6503] 2
[13] Elena Grigorescu, Akash Kumar, and Karl Wimmer: Flipping out with many
flips: Hardness of testing 𝑘-monotonicity. SIAM J. Comput., 33(4):2111–2125, 2019.
[doi:10.1137/18M1217978] 3, 4, 15
[14] Siyao Guo and Ilan Komargodski: Negation-limited formulas. Theoret. Comput. Sci.,
660:75–85, 2017. [doi:10.1016/j.tcs.2016.11.027] 3
[15] Siyao Guo, Tal Malkin, Igor C Oliveira, and Alon Rosen: The power of negations in
cryptography. In Proc. Theory of Cryptography Conf. (TCC’15), pp. 36–65. Springer, 2015.
[doi:10.1007/978-3-662-46494-6_3] 3
[16] Danny Harnik and Ran Raz: Higher lower bounds on monotone size. In Proc. 32nd STOC,
pp. 378–387. ACM Press, 2000. [doi:10.1145/335305.335349] 2
[17] Wassily Hoeffding: Probability inequalities for sums of bounded random variables. J. Amer.
Statistical Assoc., 58(301):13–30, 1963. Also available in The Collected Works of Wassily
Hoeffding, 1994, pp. 409–426, Springer and at JSTOR. See also Theorem 1 in Clayton Scott’s
lecture notes, U. Michigan, 2014. [doi:10.1080/01621459.1963.10500830] 8
[18] Chengyu Lin and Shengyu Zhang: Sensitivity conjecture and log-rank conjecture for
functions with small alternating numbers. In Proc. 44th Internat. Colloq. on Automata,
Languages, and Programming (ICALP’17), pp. 51:1–13. Schloss Dagstuhl–Leibniz-Zentrum
fuer Informatik, 2017. [doi:10.4230/LIPIcs.ICALP.2017.51] 3
[19] Nathan Linial, Yishay Mansour, and Noam Nisan: Constant depth circuits, Fourier
transform, and learnability. J. ACM, 40(3):607–620, 1993. [doi:10.1145/174130.174138] 5, 15
[20] Andrey A Markov: On the inversion complexity of a system of functions. J. ACM,
5(4):331–334, 1958. [doi:10.1145/320941.320945] 2, 6
[21] Ryan O’Donnell: Analysis of Boolean Functions. Cambridge Univ. Press, 2014.
[doi:10.1017/CBO9781139814782, arXiv:2105.10386] 13, 15
[22] Ryan O’Donnell and Karl Wimmer: KKL, Kruskal-Katona, and monotone nets. SIAM J.
Comput., 42(6):2375–2399, 2013. Preliminary version in FOCS’09. [doi:10.1137/100787325] 8
[23] Alexander A Razborov: Lower bounds for the monotone complexity of some Boolean
functions. Soviet Math. Doklady, 31:354–357, 1985. Russian original at Mathnet.ru. 2
[24] Benjamin Rossman: Correlation bounds against monotone NC1 . In Proc. 30th Comput.
Complexity Conf. (CCC’15), pp. 392–411. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik,
2015. [doi:10.4230/LIPIcs.CCC.2015.392] 3
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 17
Z HIHUAI C HEN , S IYAO G UO , Q IAN L I , C HENGYU L IN , AND X IAOMING S UN
[25] Murali K Srinivasan: Symmetric chains, Gelfand–Tsetlin chains, and the Terwilliger
algebra of the binary Hamming scheme. J. Algebraic Combinatorics, 34(2):301–322, 2011.
[doi:10.1007/s10801-010-0272-2] 5, 7
[26] Éva Tardos: The gap between monotone and non-monotone circuit complexity is exponen-
tial. Combinatorica, 8(1):141–142, 1988. [doi:10.1007/BF02122563] 2
AUTHORS
Zhihuai Chen
Researcher
Institute of Computing Technology
Chinese Academy of Sciences
Haidian District, Beijing, China
chenzhihuai outlook com
https://chenzhihuai.github.io/
Siyao Guo
Assistant Professor
Computer Science, NYU Shanghai
Pudong Xinqu, Shanghai, China
siyao guo nyu edu
https://sites.google.com/site/siyaoguo/
Qian Li
Research Scientist
Shenzhen International Center For Industrial And Applied Mathematics
Shenzhen Research Institute of Big Data
Shenzhen, Guangdong Province, China
liqian ict gmail com
https://www.sribd.cn/en/teacher/936
Chengyu Lin
Cryptographic Engineer
Espresso Systems
Menlo Park, CA, USA
linmrain gmail com
https://www.linkedin.com/in/chengyu-lin-3aa7687b/
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 18
N EW D ISTINGUISHERS FOR N EGATION -L IMITED W EAK P SEUDORANDOM F UNCTIONS
Xiaoming Sun
Professor
Institute of Computing Technology
Chinese Academy of Sciences
Haidian District, Beijing, China
sunxiaoming ict ac cn
http://theory.ict.ac.cn/sunxiaoming
ABOUT THE AUTHORS
Zhihuai Chen received his Ph. D. from the Institute of Computing Technology,
Chinese Academy of Sciences under the supervision of Xiaoming Sun. He has
worked on game theory and mechanism design. Recently he has been working
on a scheduling problem.
Siyao Guo is an assistant professor of Computer Science at NYU Shanghai. She
received her Ph. D. from the Chinese University of Hong Kong, advised by
Andrej Bogdanov. Her research interests include computational complexity,
cryptography and pseudorandomness.
Qian Li is a research scientist at the Shenzhen International Center For Industrial
And Applied Mathematics, Shenzhen Research Institute of Big Data. Previously
he was an engineer at the Alibaba Group. He received his Ph. D. in 2018 from
the Institute of Computing Technology, Chinese Academy of Sciences under the
supervision of Xiaoming Sun. He has worked on algorithms, Boolean function
analysis, quantum computing, and auction theory. He is currently interested in
algorithms and machine learning.
Chengyu Lin is a cryptographic engineer at Espresso Systems. He received his Ph. D.
from Columbia University, advised by Tal Malkin. He works on multiparty
computation, private information retrieval and lattice cryptography.
Xiaoming Sun is a professor at the Institute of Computing Technology, Chinese
Academy of Sciences. He received his Ph. D. in 2005 from Tsinghua University,
advised by Andrew Yao. He is currently interested in quantum computing.
T HEORY OF C OMPUTING, Volume 20 (2), 2024, pp. 1–19 19