Volume 20 (2024) Article 2 pp. 1-19

New Distinguishers for Negation-Limited Weak Pseudorandom Functions

by Zhihuai Chen, Siyao Guo, Qian Li, Chengyu Lin, and Xiaoming Sun

Received: March 13, 2021
Revised: August 1, 2022
Published: July 29, 2024

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.

DOI: 10.4086/toc.2024.v020a002

© 2024 Zhihuai Chen, Siyao Guo, Qian Li, Chengyu Lin, and Xiaoming Sun
Licensed under a Creative Commons Attribution License (CC-BY)