Circuit Lower Bounds for the p-Spin Optimization Problem

#### David Gamarnik, Aukosh Jagannath, Alexander S. Wein

2024, v.30, Issue 1, 81-96

ABSTRACT

We consider the problem of finding a near ground state of a p-spin

model with Rademacher couplings by means of a low-depth circuit. As a direct

extension of the authors' recent work [GJW20], we establish that any poly-size

n-output circuit that produces a spin assignment with objective value within a

certain constant factor of optimality, must have depth at least log n=(2 log log n)

as n grows. This is stronger than the known state of the art bounds of the

form

(log n=(k(n) log log n)) for similar combinatorial optimization problems,

where k(n) depends on the optimality value. For example, for the largest clique

problem k(n) corresponds to the square of the size of the clique [Ros10]. At the

same time our results are not quite comparable since in our case the circuits are

required to produce a solution itself rather than solving the associated decision

problem. As in our earlier work [GJW20], the approach is based on the overlap

gap property (OGP) exhibited by random p-spin models, but the derivation of

the circuit lower bound relies further on standard facts from Fourier analysis

on the Boolean cube, in particular the Linial-Mansour-Nisan Theorem. To the

best of our knowledge, this is the first instance when methods from spin glass

theory have ramifications for circuit complexity.

doi:10.61102/1024-2953-mprf.2024.30.1.003

Keywords: spin glasses, overlap gap property, combinatorial optimization, boolean circuits, average-case hardness

COMMENTS

Please log in or register to leave a comment