New Distinguishers for Negation-Limited Weak Pseudorandom Functions

2022/03/23 by Zhihuai Chen, Chen, Zhihuai, Siyao Guo +7
Computer Science · #Machine Learning and Algorithms #Adversarial Robustness in Machine Learning #Wireless Signal Modulation Classification

paper · pdf · doi:10.48550/arxiv.2203.12246

Abstract

We show how to distinguish circuits with log k negations (a.k.a k-monotone functions) from uniformly random functions in exp(O(n^1/3k^2/3)) time using random samples. The previous best distinguisher, due to the learning algorithm by Blais, Cannone, Oliveira, Servedio, and Tan (RANDOM'15), requires exp(O(n^1/2 k)) 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.

Related

• Learning circuits with few negations
• Properly learning monotone functions via local reconstruction
• Learning algorithms from circuit lower bounds
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier
• Pseudorandomness for Read-Once, Constant-Depth Circuits