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