论文标题
否定限制的弱伪函数的新区别
New Distinguishers for Negation-Limited Weak Pseudorandom Functions
论文作者
论文摘要
我们展示了如何用$ \ log k $ negations（又称$ k $ - 单酮函数）与$ \ exp \ left（\ tilde {o} \ left（n^{1/3} k^{1/3} k^{2/3} \ right）$使用随机样品的时间。以前的最佳区别者是由于Blais，Cannone，Oliveira，Serveio和Tan（Random'15）的学习算法，需要$ \ exp \ big（\ tilde {o} {o}（n^{1/2} k）k）\ big）$。 我们的区别者基于对\ emph {boolean cube}的傅立叶分析。我们表明，一些“中间”否定限制电路具有强烈的低度傅立叶浓度，然后我们在切片上应用了经典的外线，Mansour和Nisan“低度算法”（JACM'93）的变体。我们的技术还会导致在均匀分布下的否定电路中略有改善的弱学习者。
We show how to distinguish circuits with $\log k$ negations (a.k.a $k$-monotone functions) from uniformly random functions in $\exp\left(\tilde{O}\left(n^{1/3}k^{2/3}\right)\right)$ time using random samples. The previous best distinguisher, due to the learning algorithm by Blais, Cannone, 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 \emph{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.
