Buchumschlag

On the Hardness of Learning Regular Expressions

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Attias, Idan, Reyzin, Lev, Srebro, Nathan, Vardi, Gal
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Machine Learning Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Learning-Augmented Algorithms for Boolean Satisfiability
von: Attias, Idan, et al.
Veröffentlicht: (2025)

Learning to Think from Multiple Thinkers
von: Joshi, Nirmit, et al.
Veröffentlicht: (2026)

A Theory of Learning with Autoregressive Chain of Thought
von: Joshi, Nirmit, et al.
Veröffentlicht: (2025)

Positive Distribution Shift as a Framework for Understanding Tractable Learning
von: Medvedev, Marko, et al.
Veröffentlicht: (2026)

Multiple Planted Structures Below $\sqrt{n}$: An SoS Integrality Gap and an SQ Lower Bound
von: Mosievskiy, Matvey, et al.
Veröffentlicht: (2026)

Noisy Interpolation Learning with Shallow Univariate ReLU Networks
von: Joshi, Nirmit, et al.
Veröffentlicht: (2023)

Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality
von: Medvedev, Marko, et al.
Veröffentlicht: (2024)

On the Computational Hardness of Transformers
von: Saha, Barna, et al.
Veröffentlicht: (2026)

Are Depth-2 Regular Expressions Hard to Intersect?
von: Ascone, Rocco, et al.
Veröffentlicht: (2025)

New Hardness Results for Low-Rank Matrix Completion
von: Chawin, Dror, et al.
Veröffentlicht: (2025)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
von: Amiri, Alireza, et al.
Veröffentlicht: (2025)

Improved Hardness Results for Learning Intersections of Halfspaces
von: Tiegel, Stefan
Veröffentlicht: (2024)

An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression
von: Zhou, Lijia, et al.
Veröffentlicht: (2023)

On the Hardness of Learning One Hidden Layer Neural Networks
von: Li, Shuchen, et al.
Veröffentlicht: (2024)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
von: Majumdar, Angshul
Veröffentlicht: (2026)

Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
von: Amir, Guy, et al.
Veröffentlicht: (2024)

Hardness of Maximum Likelihood Learning of DPPs
von: Grigorescu, Elena, et al.
Veröffentlicht: (2022)

Hardness of Learning Boolean Functions from Label Proportions
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes
von: Harel, Itamar, et al.
Veröffentlicht: (2025)

Provably Overwhelming Transformer Models with Designed Inputs
von: Stambler, Lev, et al.
Veröffentlicht: (2025)

On Efficiently Representing Regular Languages as RNNs
von: Svete, Anej, et al.
Veröffentlicht: (2024)

Generalized and Unified Equivalences between Hardness and Pseudoentropy
von: Hu, Lunjia, et al.
Veröffentlicht: (2025)

Reinforced Generation of Combinatorial Structures: Hardness of Approximation
von: Nagda, Ansh, et al.
Veröffentlicht: (2025)

Subquadratic Algorithms and Hardness for Attention with Any Temperature
von: Gupta, Shreya, et al.
Veröffentlicht: (2025)

On the Hardness of Approximation of the Fair k-Center Problem
von: Thejaswi, Suhas
Veröffentlicht: (2026)

Cryptographic Hardness of Score Estimation
von: Song, Min Jae
Veröffentlicht: (2024)

Decision Tree Learning on Product Spaces
von: Moakahr, Arshia Soltani, et al.
Veröffentlicht: (2026)

Smoothed Agnostic Learning of Halfspaces over the Hypercube
von: Kou, Yiwen, et al.
Veröffentlicht: (2025)

Polyhedral Instability Governs Regret in Online Learning
von: Li, Yuetai, et al.
Veröffentlicht: (2026)

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
von: Chandrasekaran, Gautam, et al.
Veröffentlicht: (2024)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
von: Rohatgi, Dhruv, et al.
Veröffentlicht: (2025)

Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
von: Jacot, Arthur
Veröffentlicht: (2025)

Parameterized Hardness of Zonotope Containment and Neural Network Verification
von: Froese, Vincent, et al.
Veröffentlicht: (2025)

Hardness of Regular Expression Matching with Extensions
von: Nogami, Taisei, et al.
Veröffentlicht: (2026)

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

Provable Tempered Overfitting of Minimal Nets and Typical Nets
von: Harel, Itamar, et al.
Veröffentlicht: (2024)

Unique Hard Attention: A Tale of Two Sides
von: Jerad, Selim, et al.
Veröffentlicht: (2025)

Training Neural Networks is NP-Hard in Fixed Dimension
von: Froese, Vincent, et al.
Veröffentlicht: (2023)

Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classification
von: Zhu, Xiaohan, et al.
Veröffentlicht: (2025)

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
von: Merrill, William, et al.
Veröffentlicht: (2025)