Circuit lower bounds for the p-spin optimization problem

DOI10.61102/1024-2953-MPRF.2024.30.1.003MaRDI QIDQ6604527zbMATH OpenFDO

Authors David Gamarnik, Aukosh Jagannath, Alexander S. Wein

Publication date 12 September 2024

Published in Markov Processes and Related Fields (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationBoolean circuitsspin glassesaverage-case hardnessoverlap gap property

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorial optimization (90C27) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Networks and circuits as models of computation; circuit complexity (68Q06)

This page was built for publication: Circuit lower bounds for the \(p\)-spin optimization problem

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