English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We give the first almost optimal polynomial-time proper learning algorithm ofBoolean sparse multivariate polynomial under the uniform distribution. For$s$-sparse polynomial over $n$ variables and $\epsilon=1/s^\beta$, $\beta>1$,our algorithm makes $$q_U=\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+O(\frac{1}{\beta})}+ \tildeO\left(s\right)\left(\log\frac{1}{\epsilon}\right)\log n$$ queries. Notice thatour query complexity is sublinear in $1/\epsilon$ and almost linear in $s$. Allprevious algorithms have query complexity at least quadratic in $s$ and linearin $1/\epsilon$.  We then prove the almost tight lower bound$$q_L=\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+\Omega(\frac{1}{\beta})}+\Omega\left(s\right)\left(\log\frac{1}{\epsilon}\right)\log n,$$  Applying the reduction in~\cite{Bshouty19b} with the above algorithm, we givethe first almost optimal polynomial-time tester for $s$-sparse polynomial. Ourtester, for $\beta>3.404$, makes $$\tilde O\left(\frac{s}{\epsilon}\right)$$queries.

Almost Optimal Proper Learning and Testing Polynomials