Theory of Computing
-------------------
Title     : New Distinguishers for Negation-Limited Weak Pseudorandom Functions
Authors   : Zhihuai Chen, Siyao Guo, Qian Li, Chengyu Lin, and Xiaoming Sun
Volume    : 20
Number    : 2
Pages     : 1-19
URL       : https://theoryofcomputing.org/articles/v020a002

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, Canonne, 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.