Random Max-CSPs inherit algorithmic hardness from spin glasses

DOI10.4230/LIPICS.ITCS.2023.77MaRDI QIDQ6610348zbMATH OpenFDO

Authors Chris V. Jones, Juspreet Singh Sandhu, Jonathan Shi

Publication date 25 September 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2023.77

zbMATH Keywords

constraint satisfaction problemguerra-toninelli interpolationoverlap gap propertyspin Glass

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(2)

• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• On the MCMC performance in Bernoulli group testing and the random max-set cover problem

This page was built for publication: Random Max-CSPs inherit algorithmic hardness from spin glasses

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