Buchumschlag

Discrepancy Algorithms for the Binary Perceptron

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Li, Shuangping, Schramm, Tselil, Zhou, Kangjie
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Computational Complexity Mathematical Physics Probability
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Some easy optimization problems have the overlap-gap property
von: Li, Shuangping, et al.
Veröffentlicht: (2024)

Polynomial-time sampling despite disorder chaos
von: Ma, Eric, et al.
Veröffentlicht: (2025)

Stable algorithms cannot reliably find isolated perceptron solutions
von: Gong, Shuyang, et al.
Veröffentlicht: (2026)

Spectral clustering in the Gaussian mixture block model
von: Li, Shuangping, et al.
Veröffentlicht: (2023)

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

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
von: Gamarnik, David, et al.
Veröffentlicht: (2026)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2026)

Parameter estimation for Gibbs distributions
von: Harris, David G., et al.
Veröffentlicht: (2020)

Detection of local geometry in random graphs: information-theoretic and computational limits
von: Bok, Jinho, et al.
Veröffentlicht: (2026)

Sharp Online Hardness for Large Balanced Independent Sets
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2025)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
von: Li, Tiange, et al.
Veröffentlicht: (2026)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
von: Huang, Neng, et al.
Veröffentlicht: (2024)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
von: Moka, Sarat, et al.
Veröffentlicht: (2026)

Random tensor isomorphism under orthogonal and unitary actions
von: Chizewer, Jeremy, et al.
Veröffentlicht: (2026)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
von: R., Abhishek Hegade K., et al.
Veröffentlicht: (2025)

Average-Case Matrix Discrepancy: Asymptotics and Online Algorithms
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2023)

Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms
von: Antoniadis, Antonios, et al.
Veröffentlicht: (2025)

Combinatorial Parameterized Algorithms for Chemical Descriptors based on Molecular Graph Sparsity
von: Conrado, Giovanna K., et al.
Veröffentlicht: (2023)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
von: Shao, Shuai, et al.
Veröffentlicht: (2023)

Hardness of sampling solutions from the Symmetric Binary Perceptron
von: Alaoui, Ahmed El, et al.
Veröffentlicht: (2024)

Microscopic Structure of Random 3-SAT: A Discrete Geometric Approach to Phase Transitions and Algorithmic Complexity
von: Zhan, Yongjian
Veröffentlicht: (2026)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
von: Tani, Seiichiro
Veröffentlicht: (2019)

Constructive l2-Discrepancy Minimization with Additive Deviations
von: Dutta, Kunal
Veröffentlicht: (2025)

Exact Algorithms for Edge Deletion to Cactus
von: Akhtar, Sheikh Shakil, et al.
Veröffentlicht: (2026)

Space Efficient Algorithms for Parameterised Problems
von: Akhtar, Sheikh Shakil, et al.
Veröffentlicht: (2025)

A Fixed-Parameter Algorithm for the Kneser Problem
von: Haviv, Ishay
Veröffentlicht: (2022)

Algorithms and complexity for monitoring edge-geodetic sets in graphs
von: Foucaud, Florent, et al.
Veröffentlicht: (2024)

Relative-error monotonicity testing
von: Chen, Xi, et al.
Veröffentlicht: (2024)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
von: Foucaud, Florent, et al.
Veröffentlicht: (2024)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
von: Foucaud, Florent, et al.
Veröffentlicht: (2023)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
von: Hellmuth, Marc, et al.
Veröffentlicht: (2023)

Sparsifying Suprema of Gaussian Processes
von: De, Anindya, et al.
Veröffentlicht: (2024)

Low-degree estimation thresholds in planted hypergraphs and tensor PCA
von: Fu, Daniel, et al.
Veröffentlicht: (2026)

A computational phase transition for learning-to-sample from Ising models
von: Risteski, Andrej, et al.
Veröffentlicht: (2026)

Testing Convex Truncation
von: De, Anindya, et al.
Veröffentlicht: (2023)

Strong Low Degree Hardness for the Number Partitioning Problem
von: Mallarapu, Rushil, et al.
Veröffentlicht: (2025)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
von: Sohn, Youngtak, et al.
Veröffentlicht: (2025)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2024)