Buchumschlag

Unifying Formal Explanations: A Complexity-Theoretic Perspective

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bassan, Shahaf, Huang, Xuanxiang, Katz, Guy
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Machine Learning Computational Complexity Data Structures and Algorithms Optimization and Control
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A Control-Theoretic Perspective on Optimal High-Order Optimization
von: Lin, Tianyi, et al.
Veröffentlicht: (2019)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
von: Blanchard, Moise
Veröffentlicht: (2024)

Efficient Convex Optimization Requires Superlinear Memory
von: Marsden, Annie, et al.
Veröffentlicht: (2022)

A Continuous-Time Perspective on Global Acceleration for Monotone Equation Problems
von: Lin, Tianyi, et al.
Veröffentlicht: (2022)

A note on the complexity of the picker routing problem in multi-block warehouses and related problems
von: Prunet, Thibault, et al.
Veröffentlicht: (2023)

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
von: Kurpisz, Adam, et al.
Veröffentlicht: (2026)

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
von: Chen, Shengminjie, et al.
Veröffentlicht: (2026)

Solving convex QPs with structured sparsity under indicator conditions
von: Bienstock, Daniel, et al.
Veröffentlicht: (2024)

Centrality of shortest paths: Algorithms and complexity results
von: Phosavanh, Johnson, et al.
Veröffentlicht: (2024)

Min-Max Optimization Requires Exponentially Many Queries
von: Bernasconi, Martino, et al.
Veröffentlicht: (2026)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting
von: Gribanov, Dmitry, et al.
Veröffentlicht: (2026)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2022)

Is nasty noise actually harder than malicious noise?
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Adaptive and oblivious statistical adversaries are equivalent
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

Simultaneous Network Design with Restricted Link Usage
von: Kakimura, Naonori, et al.
Veröffentlicht: (2025)

Semidefinite programming and linear equations vs. homomorphism problems
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2023)

Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version)
von: Cherniavskii, M., et al.
Veröffentlicht: (2024)

A Distributional-Lifting Theorem for PAC Learning
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Local vs. Global Interpretability: A Computational Complexity Perspective
von: Bassan, Shahaf, et al.
Veröffentlicht: (2024)

Computational-Statistical Tradeoffs from NP-hardness
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective
von: Diakonikolas, Jelena, et al.
Veröffentlicht: (2024)

Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
von: Fountoulakis, Kimon, et al.
Veröffentlicht: (2026)

A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
von: Diaby, Moustapha
Veröffentlicht: (2016)

Samplability makes learning easier
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

The Sample Complexity of Replicable Realizable PAC Learning
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2026)

The Computational Complexity of Almost Stable Clustering with Penalties
von: Khodamoradi, Kamyar, et al.
Veröffentlicht: (2025)

Efficient approximation schemes for scheduling on a stochastic number of machines
von: Epstein, Leah, et al.
Veröffentlicht: (2024)

Convergence analysis of wide shallow neural operators within the framework of Neural Tangent Kernel
von: Xu, Xianliang, et al.
Veröffentlicht: (2024)

Additive Models Explained: A Computational Complexity Approach
von: Bassan, Shahaf, et al.
Veröffentlicht: (2025)

A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives
von: Grigorescu, Elena, et al.
Veröffentlicht: (2024)

Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities
von: Su, Yuexin, et al.
Veröffentlicht: (2025)

Noise Stability Optimization for Finding Flat Minima: A Hessian-based Regularization Approach
von: Zhang, Hongyang R., et al.
Veröffentlicht: (2023)

Theoretical limitations of multi-layer Transformer
von: Chen, Lijie, et al.
Veröffentlicht: (2024)

Constrained and Composite Sampling via Proximal Sampler
von: Dang, Thanh, et al.
Veröffentlicht: (2026)

Robust Learning of a Group DRO Neuron
von: Cao, Guyang, et al.
Veröffentlicht: (2026)

Online Linear Programming with Replenishment
von: Chen, Yuze, et al.
Veröffentlicht: (2026)

Non-Stationary Online Resource Allocation: Learning from a Single Sample
von: Feng, Yiding, et al.
Veröffentlicht: (2026)

Negative Momentum for Convex-Concave Optimization
von: Shugart, Henry, et al.
Veröffentlicht: (2026)

Convex Optimization with Nested Evolving Feasible Sets
von: M., Karthick Krishna, et al.
Veröffentlicht: (2026)