Copertina

New Hardness Results for Low-Rank Matrix Completion

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Chawin, Dror, Haviv, Ishay
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity Machine Learning
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Nearly Orthogonal Sets over Finite Fields
di: Chawin, Dror, et al.
Pubblicazione: (2024)

Kernelization Bounds for Constrained Coloring
di: Haviv, Ishay
Pubblicazione: (2026)

The Chromatic Number of Kneser Hypergraphs via Consensus Division
di: Haviv, Ishay
Pubblicazione: (2023)

A Fixed-Parameter Algorithm for the Kneser Problem
di: Haviv, Ishay
Pubblicazione: (2022)

Improved Approximation Algorithms for Index Coding
di: Chawin, Dror, et al.
Pubblicazione: (2024)

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

Improved Hardness Results for Learning Intersections of Halfspaces
di: Tiegel, Stefan
Pubblicazione: (2024)

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

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
di: Alman, Josh, et al.
Pubblicazione: (2025)

On the Hardness of Learning Regular Expressions
di: Attias, Idan, et al.
Pubblicazione: (2025)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
di: Amiri, Alireza, et al.
Pubblicazione: (2025)

Constant Bit-size Transformers Are Turing Complete
di: Li, Qian, et al.
Pubblicazione: (2025)

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

Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
di: Amir, Guy, et al.
Pubblicazione: (2024)

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

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

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

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

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

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

Generalized and Unified Equivalences between Hardness and Pseudoentropy
di: Hu, Lunjia, et al.
Pubblicazione: (2025)

On the Hardness of Learning One Hidden Layer Neural Networks
di: Li, Shuchen, et al.
Pubblicazione: (2024)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
di: Chukhin, Nikolai, et al.
Pubblicazione: (2024)

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

Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
di: Klivans, Adam R., et al.
Pubblicazione: (2026)

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

Ranking Vectors Clustering: Theory and Applications
di: Fattahi, Ali, et al.
Pubblicazione: (2025)

Hardness of Maximum Likelihood Learning of DPPs
di: Grigorescu, Elena, et al.
Pubblicazione: (2022)

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

Reinforced Generation of Combinatorial Structures: Hardness of Approximation
di: Nagda, Ansh, et al.
Pubblicazione: (2025)

Subquadratic Algorithms and Hardness for Attention with Any Temperature
di: Gupta, Shreya, et al.
Pubblicazione: (2025)

On the Hardness of Approximation of the Fair k-Center Problem
di: Thejaswi, Suhas
Pubblicazione: (2026)

Hardness of Learning Boolean Functions from Label Proportions
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

Cryptographic Hardness of Score Estimation
di: Song, Min Jae
Pubblicazione: (2024)

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

Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
di: Bertschinger, Daniel, et al.
Pubblicazione: (2022)

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

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

Parameterized Hardness of Zonotope Containment and Neural Network Verification
di: Froese, Vincent, et al.
Pubblicazione: (2025)

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems
di: Cao, Yang, et al.
Pubblicazione: (2024)