正态(或高斯或高斯或拉普拉斯-高斯)分布是实值随机变量的一种连续概率分布。高斯分布具有一些独特的属性,这些属性在分析研究中很有价值。 例如,法线偏差的固定集合的任何线性组合就是法线偏差。 当相关变量呈正态分布时,许多结果和方法(例如不确定性的传播和最小二乘参数拟合)都可以以显式形式进行分析得出。

最新论文

A polynomial threshold function (PTF) $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is a function of the form $f(x) = \mathsf{sign}(p(x))$ where $p$ is a polynomial of degree at most $d$. PTFs are a classical and well-studied complexity class with applications across complexity theory, learning theory, approximation theory, quantum complexity and more. We address the question of designing pseudorandom generators (PRG) for polynomial threshold functions (PTFs) in the gaussian space: design a PRG that takes a seed of few bits of randomness and outputs a $n$-dimensional vector whose distribution is indistinguishable from a standard multivariate gaussian by a degree $d$ PTF. Our main result is a PRG that takes a seed of $d^{O(1)}\log ( n / \varepsilon)\log(1/\varepsilon)/\varepsilon^2$ random bits with output that cannot be distinguished from $n$-dimensional gaussian distribution with advantage better than $\varepsilon$ by degree $d$ PTFs. The best previous generator due to O'Donnell, Servedio, and Tan (STOC'20) had a quasi-polynomial dependence (i.e., seedlength of $d^{O(\log d)}$) in the degree $d$. Along the way we prove a few nearly-tight structural properties of restrictions of PTFs that may be of independent interest.

0
0
下载
预览
参考链接
Top