Cover Image

Sparsifying Suprema of Gaussian Processes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	De, Anindya, Nadimpalli, Shivam, O'Donnell, Ryan, Servedio, Rocco A.
Format:	Preprint
Published:	2024
Subjects:	Machine Learning Computational Complexity Data Structures and Algorithms Probability
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Testing Convex Truncation
by: De, Anindya, et al.
Published: (2023)

Detecting Low-Degree Truncation
by: De, Anindya, et al.
Published: (2024)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

Testing noisy low-degree polynomials for sparsity
by: Bao, Yiqiao, et al.
Published: (2025)

Sublinear-query relative-error testing of halfspaces
by: Chen, Xi, et al.
Published: (2026)

Halfspaces are hard to test with relative error
by: Chen, Xi, et al.
Published: (2025)

Model-agnostic super-resolution in high dimensions
by: Chen, Xi, et al.
Published: (2025)

Testing Sumsets is Hard
by: Chen, Xi, et al.
Published: (2024)

Relative-error monotonicity testing
by: Chen, Xi, et al.
Published: (2024)

Is nasty noise actually harder than malicious noise?
by: Blanc, Guy, et al.
Published: (2025)

No Price Tags? No Problem: Query Strategies for Unpriced Information
by: Nadimpalli, Shivam, et al.
Published: (2025)

Learning Functions of Halfspaces
by: Alman, Josh, et al.
Published: (2026)

A computational phase transition for learning-to-sample from Ising models
by: Risteski, Andrej, et al.
Published: (2026)

DNF formulas are efficiently testable with relative error
by: Chen, Xi, et al.
Published: (2026)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2024)

Uniformity testing when you have the source code
by: Canonne, Clément L., et al.
Published: (2024)

Faster exact learning of k-term DNFs with membership and equivalence queries
by: Alman, Josh, et al.
Published: (2025)

DNF Learning via Locally Mixing Random Walks
by: Alman, Josh, et al.
Published: (2025)

Tensor cumulants for statistical inference on invariant distributions
by: Kunisky, Dmitriy, et al.
Published: (2024)

Detection of local geometry in random graphs: information-theoretic and computational limits
by: Bok, Jinho, et al.
Published: (2026)

Relative-error testing of conjunctions and decision lists
by: Chen, Xi, et al.
Published: (2025)

Testing Juntas and Junta Subclasses with Relative Error
by: Chen, Xi, et al.
Published: (2025)

No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore
by: Kothari, Robin, et al.
Published: (2025)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
by: Huang, Neng, et al.
Published: (2024)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
by: Moka, Sarat, et al.
Published: (2026)

Random tensor isomorphism under orthogonal and unitary actions
by: Chizewer, Jeremy, et al.
Published: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
by: Li, Tiange, et al.
Published: (2026)

Relative-error unateness testing
by: Chen, Xi, et al.
Published: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

Some easy optimization problems have the overlap-gap property
by: Li, Shuangping, et al.
Published: (2024)

Polynomial-time sampling despite disorder chaos
by: Ma, Eric, et al.
Published: (2025)

Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
by: Hsieh, Jun-Ting, et al.
Published: (2024)

Instance-Optimal Quantum State Certification with Entangled Measurements
by: O'Donnell, Ryan, et al.
Published: (2025)

Superconstant Inapproximability of Decision Tree Learning
by: Koch, Caleb, et al.
Published: (2024)

Fast decision tree learning solves hard coding-theoretic problems
by: Koch, Caleb, et al.
Published: (2024)

Adaptive and oblivious statistical adversaries are equivalent
by: Blanc, Guy, et al.
Published: (2024)

Private graphon estimation via sum-of-squares
by: Chen, Hongjie, et al.
Published: (2024)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
by: Gopalan, Parikshit, et al.
Published: (2024)

On the Power of Interactive Proofs for Learning
by: Gur, Tom, et al.
Published: (2024)

Low-degree phase transitions for detecting a planted clique in sublinear time
by: Mardia, Jay, et al.
Published: (2024)