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

These notes survey and explore an emerging method, which we call thelow-degree method, for predicting and understandingstatistical-versus-computational tradeoffs in high-dimensional inferenceproblems. In short, the method posits that a certain quantity -- the secondmoment of the low-degree likelihood ratio -- gives insight into how muchcomputational time is required to solve a given hypothesis testing problem,which can in turn be used to predict the computational hardness of a variety ofstatistical inference tasks. While this method originated in the study of thesum-of-squares (SoS) hierarchy of convex programs, we present a self-containedintroduction that does not require knowledge of SoS. In addition to showing howto carry out predictions using the method, we include a discussioninvestigating both rigorous and conjectural consequences of these predictions.  These notes include some new results, simplified proofs, and refinedconjectures. For instance, we point out a formal connection between spectralmethods and the low-degree likelihood ratio, and we give a sharp low-degreelower bound against subexponential-time algorithms for tensor PCA.

Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio