conftrace_

low-degree polynomial

17 papers

Explore in graph

Also known as

LDP

Co-occurring keywords

planted clique (17) hypothesis testing (254) phase transition (92) statistical query (50) sample complexity (1169) belief propagation (177) broadcasting on tree (1) kesten stigum bound (1) sparsity level (3) shallow neural network (18)

Papers

Shallow Neural Networks Learn Low-Degree Spherical Polynomials with Feature Learning by Learnable Channel Attention ALT 2026
Low-degree phase transitions for detecting a planted clique in sublinear time COLT 2024
Testable Learning with Distribution Shift COLT 2024
Computational-Statistical Gaps in Gaussian Single-Index Models (Extended Abstract) COLT 2024
Computation-information gap in high-dimensional clustering COLT 2024
Low Degree Hardness for Broadcasting on Trees NIPS 2024
Is Planted Coloring Easier than Planted Clique? COLT 2023
Detection-Recovery Gap for Planted Dense Cycles COLT 2023
Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression COLT 2023
On the well-spread property and its relation to linear regression COLT 2022
Statistical and Computational Phase Transitions in Group Testing COLT 2022
Reconstruction on Trees and Low-Degree Polynomials NIPS 2022
Lattice-Based Methods Surpass Sum-of-Squares in Clustering COLT 2022
Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent COLT 2021
Hypothesis testing with low-degree polynomials in the Morris class of exponential families COLT 2021
On the Connection Between Learning Two-Layer Neural Networks and Tensor Decomposition AISTATS 2019
Tight Bounds on $\ell_1$ Approximation and Learning of Self-Bounding Functions ALT 2017