Low-degree hardness of random optimization problems

DOI10.1109/FOCS46700.2020.00021MaRDI QIDQ6944036zbMATH OpenFDO

Authors David Gamarnik, Aukosh Jagannath, Alexander S. Wein

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS46700.2020.00021

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(9)

• Precise error rates for computationally efficient testing
• Low coordinate degree algorithms. I: Universality of computational thresholds for hypothesis testing
• SQ lower bounds for random sparse planted vector problem
• The low-degree hardness of finding large independent sets in sparse random hypergraphs
• Near-optimal shattering in the Ising pure p-spin and rarity of solutions returned by stable algorithms
• Low-degree hardness of detection for correlated Erdős-Rényi graphs
• Shattering in the Ising p-spin glass model
• Counting stars is constant-degree optimal for detecting any planted subgraph
• Bounds on the ground state energy of quantum p-spin Hamiltonians

This page was built for publication: Low-degree hardness of random optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6944036)