Image de couverture de livre

Stable algorithms cannot reliably find isolated perceptron solutions

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Gong, Shuyang, Huang, Brice, Li, Shuangping, Sellke, Mark
Format:	Preprint
Publié:	2026
Sujets:	Computational Complexity Data Structures and Algorithms Mathematical Physics Probability
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Discrepancy Algorithms for the Binary Perceptron
par: Li, Shuangping, et autres
Publié: (2024)

Some easy optimization problems have the overlap-gap property
par: Li, Shuangping, et autres
Publié: (2024)

Strong Low Degree Hardness for the Number Partitioning Problem
par: Mallarapu, Rushil, et autres
Publié: (2025)

Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT
par: Kızıldağ, Eren C.
Publié: (2023)

Parameter estimation for Gibbs distributions
par: Harris, David G., et autres
Publié: (2020)

Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses
par: Sellke, Mark
Publié: (2025)

Detection of local geometry in random graphs: information-theoretic and computational limits
par: Bok, Jinho, et autres
Publié: (2026)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
par: Grossman, Ofer, et autres
Publié: (2023)

Strong Low Degree Hardness for Stable Local Optima in Spin Glasses
par: Huang, Brice, et autres
Publié: (2025)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
par: Gamarnik, David, et autres
Publié: (2026)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
par: Dhawan, Abhishek, et autres
Publié: (2026)

Sharp Online Hardness for Large Balanced Independent Sets
par: Dhawan, Abhishek, et autres
Publié: (2025)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
par: Huang, Neng, et autres
Publié: (2024)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
par: Li, Tiange, et autres
Publié: (2026)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
par: Moka, Sarat, et autres
Publié: (2026)

Random tensor isomorphism under orthogonal and unitary actions
par: Chizewer, Jeremy, et autres
Publié: (2026)

Cycling in the forest with Wilson's algorithm
par: Fanuel, Michaël, et autres
Publié: (2024)

On Stable Cutsets in General and Minimum Degree Constrained Graphs
par: Vroon, Mats, et autres
Publié: (2025)

Polynomial-time sampling despite disorder chaos
par: Ma, Eric, et autres
Publié: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
par: Kunisky, Dmitriy, et autres
Publié: (2024)

A general framework for finding diverse solutions via network flow and its applications
par: Iwamasa, Yuni, et autres
Publié: (2025)

Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries
par: Chen, Mark, et autres
Publié: (2025)

On zeros and algorithms for disordered systems: mean-field spin glasses
par: Bencs, Ferenc, et autres
Publié: (2025)

Relative-error monotonicity testing
par: Chen, Xi, et autres
Publié: (2024)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
par: DeHaan, Ian, et autres
Publié: (2025)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
par: Foucaud, Florent, et autres
Publié: (2023)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
par: Foucaud, Florent, et autres
Publié: (2024)

Low-degree estimation thresholds in planted hypergraphs and tensor PCA
par: Fu, Daniel, et autres
Publié: (2026)

A computational phase transition for learning-to-sample from Ising models
par: Risteski, Andrej, et autres
Publié: (2026)

Sparsifying Suprema of Gaussian Processes
par: De, Anindya, et autres
Publié: (2024)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
par: R., Abhishek Hegade K., et autres
Publié: (2025)

Testing Convex Truncation
par: De, Anindya, et autres
Publié: (2023)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
par: Sohn, Youngtak, et autres
Publié: (2025)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

A note on approximating the average degree of bounded arboricity graphs
par: Eden, Talya, et autres
Publié: (2026)

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
par: Hamm, Thekla, et autres
Publié: (2026)

Breadth-First Search Trees with Many or Few Leaves
par: Beisegel, Jesse, et autres
Publié: (2026)

On the parameterized complexity of Broadcast Independence and Broadcast Packing
par: Dumont, Joanne, et autres
Publié: (2026)

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
par: Dreier, Jan, et autres
Publié: (2026)

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
par: Das, Avinandan
Publié: (2026)