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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Consider the setting where a $\rho$-sparse Rademacher vector is planted in arandom $d$-dimensional subspace of $R^n$. A classical question is how torecover this planted vector given a random basis in this subspace. A recentresult by [ZSWB21] showed that the Lattice basis reduction algorithm canrecover the planted vector when $n\geq d+1$. Although the algorithm is notexpected to tolerate inverse polynomial amount of noise, it is surprisingbecause it was previously shown that recovery cannot be achieved by low degreepolynomials when $n\ll \rho^2 d^{2}$ [MW21]. A natural question is whether wecan derive an Statistical Query (SQ) lower bound matching the previous lowdegree lower bound in [MW21]. This will  - imply that the SQ lower bound can be surpassed by lattice based algorithms;  - predict the computational hardness when the planted vector is perturbed byinverse polynomial amount of noise. In this paper, we prove such an SQ lowerbound. In particular, we show that super-polynomial number of VSTAT queries isneeded to solve the easier statistical testing problem when $n\ll \rho^2 d^{2}$and $\rho\gg \frac{1}{\sqrt{d}}$. The most notable technique we used to derivethe SQ lower bound is the almost equivalence relationship between SQ lowerbound and low degree lower bound [BBH+20, MW21].

SQ Lower Bounds for Random Sparse Planted Vector Problem