On the Probabilistic Degrees of Symmetric Boolean functions
On the Probabilistic Degrees of Symmetric Boolean functions
复制标题
论对称布尔函数的概率度
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
S. Venkitesh
中科院分区：
文献类型：
--
作者：
S. Srinivasan;Utkarsh Tripathi;S. Venkitesh
布尔函数的概率度$ f：{0,1}^n
ightarrow {0,1} $被定义为最小的$ d $，使得最多有$ d $的随机多项式$ MATHBF {p} $，每个点都与$ f $一致。由Razborov（1987）引入的，在布尔函数的概率程度上的上限和下限---特别是对称的布尔函数 - 已用于证明明确的下限，设计伪和发电机，并设计算法用于组合问题。
在本文中，我们表征了所有对称布尔函数的概率程度，直至固定特征（正或零）的所有领域，均具有多群因子。
The probabilistic degree of a Boolean function $f:{0,1}^n
ightarrow {0,1}$ is defined to be the smallest $d$ such that there is a random polynomial $mathbf{P}$ of degree at most $d$ that agrees with $f$ at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees of Boolean functions --- specifically symmetric Boolean functions --- have been used to prove explicit lower bounds, design pseudorandom generators, and devise algorithms for combinatorial problems.
In this paper, we characterize the probabilistic degrees of all symmetric Boolean functions up to polylogarithmic factors over all fields of fixed characteristic (positive or zero).