:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Chawin, Dror, Haviv, Ishay
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Machine Learning
Online Access:	https://arxiv.org/abs/2506.18440
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Kernelization Bounds for Constrained Coloring
by: Haviv, Ishay
Published: (2026)

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

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

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

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

Improved Hardness Results for Learning Intersections of Halfspaces
by: Tiegel, Stefan
Published: (2024)

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

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

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

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

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

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

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

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)

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

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

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

A Near-Optimal Kernel for a Coloring Problem
by: Haviv, Ishay, et al.
Published: (2025)

Kernelization for Orthogonality Dimension
by: Haviv, Ishay, et al.
Published: (2024)

Cryptographic Hardness of Score Estimation
by: Song, Min Jae
Published: (2024)

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

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

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

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

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