论文标题
几乎最佳的适当学习和测试多项式
Almost Optimal Proper Learning and Testing Polynomials
论文作者
论文摘要
我们在均匀分布下给出了第一个几乎最佳的多项式学习算法的稀疏多元多项式。对于$ s $ -sparse多项式，$ n $变量和$ε= 1/s^β$，$β> 1 $，我们的算法使$$ q_u = \ left（\ frac {s} s}ε\ right） o \ left（s \ right）\ left（\ log \ frac {1}ε\ right）\ log n $$ queries。请注意，我们的查询复杂性为$ 1/ε$，几乎是$ s $的sublinear。所有以前的算法都至少在$ s $中至少具有二次算法，而线性为$ 1/ε$。 然后，我们证明了几乎紧密的下限$$ q_l = \ left（\ frac {s}ε\右） 使用上述算法应用〜\ cite {bshouty19b}的降低，我们为$ s $ s $ -s-sparse多项式提供了第一个几乎最佳的多项式时间测试仪。我们的测试仪以$β> 3.404 $，使$$ \ tilde o \ left（\ frac {s}ε\ right）$$查询。
We give the first almost optimal polynomial-time proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. For $s$-sparse polynomial over $n$ variables and $ε=1/s^β$, $β>1$, our algorithm makes $$q_U=\left(\frac{s}ε\right)^{\frac{\log β}β+O(\frac{1}β)}+ \tilde O\left(s\right)\left(\log\frac{1}ε\right)\log n$$ queries. Notice that our query complexity is sublinear in $1/ε$ and almost linear in $s$. All previous algorithms have query complexity at least quadratic in $s$ and linear in $1/ε$. We then prove the almost tight lower bound $$q_L=\left(\frac{s}ε\right)^{\frac{\log β}β+Ω(\frac{1}β)}+ Ω\left(s\right)\left(\log\frac{1}ε\right)\log n,$$ Applying the reduction in~\cite{Bshouty19b} with the above algorithm, we give the first almost optimal polynomial-time tester for $s$-sparse polynomial. Our tester, for $β>3.404$, makes $$\tilde O\left(\frac{s}ε\right)$$ queries.
