# New Distinguishers for Negation-Limited Weak Pseudorandom Functions

arXiv: https://arxiv.org/abs/2203.12246 · HTML: https://mlsanity.com/paper/2203.12246/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 30 references that are in the map.
- First posted on arXiv 23 Mar 2022.

## Builds on (most cited first, 2 of 2)

- [Approximate resilience, monotonicity, and the complexity of agnostic learning](https://mlsanity.com/paper/1405.5268/) (2014)
- [Learning circuits with few negations](https://mlsanity.com/paper/1410.8420/) (2014)

## Abstract (arXiv)

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