Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses Chris Jones Kunal MarwahaJuspreet Singh SandhuJonathan Shi

2025-04-29 0 0 503.68KB 41 页 10玖币

侵权投诉

Random Max-CSPs Inherit Algorithmic Hardness from Spin

Glasses

Chris Jones*Kunal Marwaha†Juspreet Singh Sandhu‡Jonathan Shi§

January 11, 2023

Abstract

We study random constraint satisfaction problems (CSPs) at large clause density. We relate

the structure of near-optimal solutions for any Boolean Max-CSP to that for an associated spin

glass on the hypercube, using the Guerra-Toninelli interpolation from statistical physics. The

noise stability polynomial of the CSP’s predicate is, up to a constant, the mixture polynomial of

the associated spin glass. We show two main consequences:

We prove that the maximum fraction of constraints that can be satisﬁed in a random

Max-CSP at large clause density is determined by the ground state energy density of

the corresponding spin glass. Since the latter value can be computed with the Parisi

formula [Par80,Tal06,AC17], we provide numerical values for some popular CSPs.

We prove that a Max-CSP at large clause density possesses generalized versions of the

overlap gap property if and only if the same holds for the corresponding spin glass. We

transfer results from [

HS21

] to obstruct algorithms with overlap concentration on a large

class of Max-CSPs. This immediately includes local classical and local quantum algorithms

[CLSS22].

Department of Computer Science, University of Chicago, Chicago, Illinois, USA. Supported by the National Science

Foundation under Grant No. CCF-2008920. Email: csj@uchicago.edu.

†

Department of Computer Science, University of Chicago, Chicago, Illinois, USA. Supported by the National Science

Foundation Graduate Research Fellowship Program under Grant No. DGE-1746045. Email: kmarw@uchicago.edu.

‡

School of Engineering & Applied Sciences, Harvard University, Cambridge, Massachusetts, USA. Supported by a Simons

Investigator Fellowship, NSF grant DMS-2134157, NSF STAQ award PHY-1818914, DARPA grant W911NF2010021,

DARPA ONISQ program award HR001120C0068 and DOE grant DE-SC0022199. Email: jus065@g.harvard.edu.

Department of Computer Science, Bocconi University, Milan, Italy. Supported by European Research Council (ERC)

award No. 834861 (SO-ReCoDi). Email: jonathan.shi@unibocconi.it.

arXiv:2210.03006v2 [cs.DM] 10 Jan 2023

Contents

1 Introduction 1

1.1 Mainresults .......................................... 1

1.2 Relatedwork.......................................... 4

2 Preliminaries 6

2.1 Random constraint satisfaction problems (CSPs) . . . . . . . . . . . . . . . . . . . . . 6

2.2 Mean-ﬁeldspinglasses.................................... 7

2.3 Solution geometry of optimization problems . . . . . . . . . . . . . . . . . . . . . . . 8

2.4 Fourier analysis on the hypercube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.5 Concentrationinequalities.................................. 11

3 Sparse and dense models have the same free energy 12

3.1 Proof of Theorem 3.5 ..................................... 14

4 Optimal value of a random Max-CSP 19

4.1 Numericalcalculations.................................... 20

5 Overlap gaps in a random Max-CSP 20

5.1 ThebranchingOGP...................................... 22

6 Implications for algorithmic hardness 23

7 Discussion 26

A Concentration Proofs 33

B Correlation functions of sparse Hamiltonians 36

C Debiasing 37

1 Introduction

In this work, we formalize a general and deep connection between two intensely studied classes

of optimization problems: constraint satisfaction problems (CSPs), studied in computer science,

and spin glass models, studied in statistical physics. We demonstrate that as the clause density

of the random CSP increases, the geometric properties of the set of nearly-optimal solutions

converge to those of a corresponding spin glass model. In these spin glass models, the very same

geometric properties imply bounds on the average-case approximability achieved by broad classes

of algorithms [

AMS21b

GJW20

GJ21

]; these bounds are conjectured to be the best possible among

all polynomial-time algorithms [

Gam21

HS21

]. The correspondence we establish here implies that

the same lower bounds apply to average-case CSPs.

CSPs are paradigmatic computational tasks. Their study has led to foundational results in

computational hardness, approximability, and optimization [

Pas13

]. In recent years, we have learned

more about CSPs through methods inspired by statistical physics, especially when the clauses of

the CSP are chosen randomly [

DSS16b

DSS16a

DMS17

Sen18

DSS22

]. By identifying the solution

quality of a variable assignment with the energy of a conﬁguration of particles, we can investigate

“physical” properties of the CSP, such as phase transitions or solution clustering at diﬀerent

temperatures. Surprisingly, these physical properties can have computational consequences.

We study random CSP instances with Boolean variables, random literal signs, and number of

constraints which is a large constant times the number of variables, such that each constraint acts

on a constant number of variables. If

is the number of variables, then

m=αn

is the number

of constraints for some constant

. For large enough

, the CSP is unsatisﬁable with probability

−on(

)

. Therefore the goal is to ﬁnd a variable assignment that maximizes the number of satisﬁed

constraints, and we think of these as Max-CSPs.

Given a random Max-CSP, how many constraints can be satisﬁed? How are the best assignments

distributed around the hypercube? Can we ﬁnd these assignments with eﬃcient algorithms?

Statistical physicists use questions like these to investigate the solution geometry of a problem. Our

main result connects the solution geometry of a Max-CSP (with large enough

) to that of a spin

glass. As a consequence, much of our mathematical and algorithmic understanding of spin glasses

transfers to CSPs at large clause density.

Aspin glass (more properly a mixed mean-ﬁeld spin glass) is a random system of

particles (variables)

speciﬁed by a mixture polynomial

ξ(s) = Pp≥1c2

psp

. In this model, the interaction strength between

every

-tuple of particles is an independent Gaussian with variance

pn1−p

; this can be thought of

as a randomly-weighted CSP on the complete

-uniform hypergraph. We show that as the clause

density of any random CSP increases (

α→ ∞

), the solution space starts to resemble that of a spin

glass. For example, Max-Cut on random graphs with large constant average degree qualitatively

looks like the Sherrington-Kirkpatrick model, where

c2=

{ci}i,2=

0 [

SK75

DMS17

]. (Note that our

proof applies to Max-2XOR instead of Max-Cut, so we do not recover this result exactly.)

1.1 Main results

Formally, we relate the free energy density of a random Max-CSP instance to that of a particular spin

glass. The associated spin glass is determined only by the Fourier weights of the CSP. In fact, the

mixture polynomial of the spin glass is, up to a constant, the noise stability polynomial of the CSP

(see Section 2 for deﬁnitions):

Theorem 1.1

(Free energy density)

Generate a random CSP instance

(with cost function

) consisting

α·n

independent and uniform constraints of a predicate

f:{±

}k→ {

0, 1

}

with randomly signed literals.

Deﬁne the polynomial

ξ(s) = Stabs(f)−b

f(∅)2=

j=1kf=jk2sj, (1)

where

Stabs(f)

is the noise stability polynomial of

, and

kf=jk2

is the Fourier weight of

at degree

Generate a random spin glass instance Hξwith mixture polynomial ξ.

Let

β >

0, and deﬁne

ZI(β) = Pσ∈{±1}nHI(σ)

and

ZSGξ(β) = Pσ∈{±1}nHξ(σ)

as the respective partition

functions. Then

βnlog ZI(β) = b

f(∅) + 1

βn

log ZSGξ(β)

√α+Oβ2

α2+on(1). (2)

where the second-to-last term (which may depend on

) satisﬁes

Oβ2

α2≤C·β2

α2

whenever

α≤ε0

for

absolute constants C,ε0>0, and the last term is random and is on(1)w.h.p.

Prior work relates the free energy density of speciﬁc CSPs such as Max-

XOR [

DMS17

Sen18

] and

Max-

SAT [

Pan18

] to that of a spin glass. Theorem 1.1 generalizes this connection to any random

Max-CSP with randomly signed literals.

The asymptotic equivalence of the free energy density implies the equivalence of several properties

of the solution geometry for large enough

. We show two speciﬁc implications of Theorem 1.1.

The ﬁrst is that the optimal value of a random Max-CSP in the large clause density limit can be

found with a spin glass calculation.

Corollary 1.2.

(Optimal value equivalence). Generate a random CSP instance

consisting of

α·n

independent and uniform constraints of a predicate

f:{±

}k→ {

0, 1

}

with randomly signed literals. Let

be the maximum fraction of constraints of

that can be satisﬁed. Let

be deﬁned as in Equation (1), and

GSED(SGξ)as the (non-random) ground state energy density of the associated spin glass. Then

vI=b

f(∅) + GSED(SGξ)

√α+o1

√α. (3)

where the last term is at most

κ(n

α)

w.h.p for a function

κ(n

α)

satisfying

κ(n

α)·√α→

0as

n→ ∞

then α→ ∞.

Computing the minimum value, or ground state energy, of a spin glass can famously be done

using the Parisi formula. In Section 4, we use the Parisi formula to compute

GSED(SGξ)

for several

common CSPs (our code is available online).

The second implication relates to algorithmic hardness.

Intuitively, when global minima are

located in clusters, some algorithms cannot eﬃciently ﬁnd them. A recent body of work (starting

For this implication, we need to boost Theorem 1.1 to interpolate the free energy density restricted to any given

overlap and correlation structure.

with [

GS14

]) has pinpointed hardness on the presence of an overlap gap property (OGP), showing how

this property obstructs noise-stable algorithms from

(

−ε)

-approximating average-case instances.

We show that a ﬂexible version of the OGP, called the branching OGP [

HS21

], exists on a spin

glass exactly when it exists on the associated Max-CSP at large enough clause density. As a result,

the techniques that obstruct algorithms on certain spin glasses also work on the corresponding

Max-CSPs.

Corollary 1.3

(OGP equivalence, informal)

Take any Max-CSP. Consider the associated spin glass

SGξ

where

is deﬁned as in Equation (1). Then

SGξ

exhibits an OGP at value

if and only if the Max-CSP

exhibits an OGP at value b

f(∅) + v

√αfor all suﬃciently large α.

The formal class of algorithms we obstruct is as follows [

HS21

]. Consider two correlated instances

with correlation parameter

t∈[

0, 1

]

. A deterministic

algorithm is overlap-concentrated if for every

, the overlap (a.k.a the Hamming distance) between the two output assignments for the two

correlated instances is concentrated inside a narrow interval. This is a notion of noise robustness

that many commonly-used algorithms have, including approximately Lipschitz algorithms on spin

glasses [

HS21

] and local classical and local quantum algorithms on random Max-CSPs [

CLSS22

Additionally, survey propagation with a constant number of message-passing rounds likely has

this property [BMZ05,Gam21,BH22].

Theorem 1.4

(OGP obstructs algorithms with overlap concentration, informal)

Consider an algorithm

with overlap concentration. Then

cannot output arbitrarily good approximate solutions on instances

of Max-CSPs which exhibit an OGP.

Our proof of Theorem 1.4 follows that of Huang and Sellke [HS21], who prove the same result on

spin glasses. Only a few changes are needed to transfer their result to Max-CSPs. Note that this

result also applies to CSPs with small αif they exhibit an OGP.

It is known that an OGP (speciﬁcally, a branching OGP) exists with high probability on spin glasses

with even mixture polynomials without quadratic terms [

CGPR19

HS21

]. Combining this with the

results that we have stated, we conclude the following:

Corollary 1.5

(informal)

Consider a random Max-CSP with a predicate

such that the only nonzero

Fourier coeﬃcients of

have even degree

j≥

4. For almost all instances of the Max-CSP, no algorithm with

overlap concentration can output (1−ε)-approximately optimal solutions for all ε > 0.

For example, this unconditionally obstructs overlap concentrated algorithms from approximating

random 4XOR instances.

Corollary 1.3 makes progress on [

CLSS22

, Problem 9.2 (arXiv version)], asking which CSPs exhibit

an OGP at large clause density. A full characterization of spin glasses with an OGP, and thereby

CSPs in the large

limit, is not complete (although spherical spin glasses have been classiﬁed [

Sub18

Proposition 1]). For example, the Sherrington-Kirkpatrick model is strongly suspected to have no

OGP, but this is not fully proven [ACZ20].

We cannot help but mention that these topological properties of the solution space (i.e. the solution

geometry) may precisely characterize the algorithmic approximability of spin glasses and random

2A randomized algorithm is overlap-concentrated if it is overlap-concentrated for every ﬁxing of the randomness.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

RandomMax-CSPsInheritAlgorithmicHardnessfromSpinGlassesChrisJones*KunalMarwahaJuspreetSinghSandhuJonathanShi§January11,2023AbstractWestudyrandomconstraintsatisfactionproblems(CSPs)atlargeclausedensity.Werelatethestructureofnear-optimalsolutionsforanyBooleanMax-CSPtothatforanassociatedspinglassonth...

展开>> 收起<<

Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses Chris Jones Kunal MarwahaJuspreet Singh SandhuJonathan Shi.pdf

共41页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses Chris Jones Kunal MarwahaJuspreet Singh SandhuJonathan Shi

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: