Cover Image

Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Klivans, Adam R., Stavropoulos, Konstantinos, Vasilyan, Arsen
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
by: Chandrasekaran, Gautam, et al.
Published: (2024)

Testable Learning with Distribution Shift
by: Klivans, Adam R., et al.
Published: (2023)

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
by: Klivans, Adam R., et al.
Published: (2024)

A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Learning Constant-Depth Circuits in Malicious Noise Models
by: Klivans, Adam R., et al.
Published: (2024)

Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
by: Klivans, Adam R., et al.
Published: (2026)

The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination
by: Klivans, Adam R., et al.
Published: (2025)

Testing Noise Assumptions of Learning Algorithms
by: Goel, Surbhi, et al.
Published: (2025)

Iterative Chow Filtering for Learning with Distribution Shift
by: Chandrasekaran, Gautam, et al.
Published: (2026)

Efficient Discrepancy Testing for Learning with Distribution Shift
by: Chandrasekaran, Gautam, et al.
Published: (2024)

Tolerant Algorithms for Learning with Arbitrary Covariate Shift
by: Goel, Surbhi, et al.
Published: (2024)

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
by: Wein, Alexander S.
Published: (2025)

The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds
by: Tsirkas, Konstantinos, et al.
Published: (2026)

Low-Rank Matrix Approximation for Neural Network Compression
by: Cherukuri, Kalyan, et al.
Published: (2025)

New Hardness Results for Low-Rank Matrix Completion
by: Chawin, Dror, et al.
Published: (2025)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
by: Luo, Yuetian, et al.
Published: (2023)

Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
by: Thornton, Mitchell A.
Published: (2026)

Robust learning of halfspaces under log-concave marginals
by: Lange, Jane, et al.
Published: (2025)

Low-degree learning and the metric entropy of polynomials
by: Eskenazis, Alexandros, et al.
Published: (2022)

Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees
by: Chandrasekaran, Gautam, et al.
Published: (2025)

The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
by: Brösamle, Moritz, et al.
Published: (2026)

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
by: Grewal, Sabee, et al.
Published: (2022)

One-Way Functions and Polynomial Time Dimension
by: Nandakumar, Satyadev, et al.
Published: (2024)

Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
by: Gui, Kaiwen, et al.
Published: (2023)

Lossless Model Compression via Joint Low-Rank Factorization Optimization
by: Zhang, Boyang, et al.
Published: (2024)

Reachability Constraints in Variational Quantum Circuits: Optimization within Polynomial Group Module
by: Oh, Yun-Tak, et al.
Published: (2026)

Low degree conjecture implies sharp computational thresholds in stochastic block model
by: Ding, Jingqiu, et al.
Published: (2025)

Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
by: Hu, Jerry Yao-Chieh, et al.
Published: (2024)

The Parameterized Complexity of Computing the VC-Dimension
by: Foucaud, Florent, et al.
Published: (2025)

When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
by: Li, Chenyang, et al.
Published: (2025)

Primitive Recursion without Composition: Dynamical Characterizations, from Neural Networks to Polynomial ODEs
by: Bournez, Olivier
Published: (2026)

What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?
by: Xu, Ruihan, et al.
Published: (2025)

Training Neural Networks is NP-Hard in Fixed Dimension
by: Froese, Vincent, et al.
Published: (2023)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
by: Majumdar, Angshul
Published: (2026)

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
by: Li, Qian, et al.
Published: (2026)

Decision Tree Learning on Product Spaces
by: Moakahr, Arshia Soltani, et al.
Published: (2026)

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
by: Jacobs, Peter Matthew, et al.
Published: (2026)

On the Computational Hardness of Transformers
by: Saha, Barna, et al.
Published: (2026)

Certifiable Boolean Reasoning Is Universal
by: Li, Wenhao, et al.
Published: (2026)