Disordered systems insights on computational hardness (Q5055432)

scientific article; zbMATH DE number 7632732

Language	Label	Description	Also known as
English	Disordered systems insights on computational hardness	scientific article; zbMATH DE number 7632732

Statements

instance of

scholarly article

0 references

title

Disordered systems insights on computational hardness (English)

0 references

0 references

0 references

0 references

Journal of Statistical Mechanics: Theory and Experiment

0 references

publication date

13 December 2022

0 references

full work available at URL

https://arxiv.org/abs/2210.08312

0 references

zbMATH Keywords

cavity and replica method

0 references

message-passing algorithms

0 references

statistical inference

0 references

typical-case computational complexity

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Q3090774

0 references

The complexity of theorem-proving procedures

0 references

Application of statistical mechanics to NP-complete problems in combinatorial optimisation

0 references

Q4012216

0 references

Determining computational complexity from characteristic ‘phase transitions’

0 references

Optimal shrinkage of eigenvalues in the spiked covariance model

0 references

Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications

0 references

Sparse Bayesian Methods for Low-Rank Matrix Estimation

0 references

On the solution-space geometry of random constraint satisfaction problems

0 references

Analysis of Boolean Functions

0 references

The overlap gap property and approximate message passing algorithms for $p$-spin models

0 references

Q4237477

0 references

The thermodynamic limit in mean field spin glass models

0 references

The Parisi formula

0 references

The Parisi ultrametricity conjecture

0 references

The Sherrington-Kirkpatrick Model

0 references

Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses

0 references

Optimization of mean-field spin glasses

0 references

Suboptimality of local algorithms for a class of max-cut problems

0 references

On the energy landscape of spherical spin glasses

0 references

Disorder chaos in some diluted spin Glass models

0 references

Limits of local algorithms over sparse random graphs

0 references

Q5302097

0 references

On the $AC^0$ Complexity of Subgraph Isomorphism

0 references

LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM

0 references

On the solution‐space geometry of random constraint satisfaction problems

0 references

Storage capacity in symmetric binary perceptrons

0 references

Frozen 1-RSB structure of the symmetric Ising perceptron

0 references

Optimal errors and phase transitions in high-dimensional generalized linear models

0 references

Statistical Physics of Spin Glasses and Information Processing

0 references

An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model

0 references

The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing

0 references

State evolution for general approximate message passing algorithms, with applications to spatial coupling

0 references

Universality in polytope phase transitions and message passing algorithms

0 references

A Limit Theorem for Multidimensional Galton-Watson Processes

0 references

Quiet Planting in the Locked Constraint Satisfaction Problems

0 references

Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection

0 references

Survey propagation: An algorithm for satisfiability

0 references

Approximate survey propagation for statistical inference

0 references

Sum-of-squares proofs and the quest toward optimal algorithms

0 references

Anneaux preordonnes

0 references

A Nullstellensatz and a Positivstellensatz in semialgebraic geometry

0 references

An approach to obtaining global extremums in polynomial mathematical programming problems

0 references

Q4496025

0 references

Global Optimization with Polynomials and the Problem of Moments

0 references

SOS Is Not Obviously Automatizable, Even Approximately

0 references

On the Bit Complexity of Sum-of-Squares Proofs

0 references

Complexity of Positivstellensatz proofs for the knapsack

0 references

Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity

0 references

Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope

0 references

Sparse sums of squares on finite abelian groups and improved semidefinite lifts

0 references

Reducibility among Combinatorial Problems

0 references

On a positive semidefinite relaxation of the cut polytope

0 references

Semidefinite programs on sparse random graphs and their application to community detection

0 references

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

0 references

Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

0 references

A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian

0 references

Lifting sum-of-squares lower bounds: degree-2 to degree-4

0 references

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

0 references

HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS

0 references

Q5875785

0 references

The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime

0 references

Rounding sum-of-squares relaxations

0 references

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

0 references

A Theory of Cooperative Phenomena

0 references

Spectral redemption in clustering sparse networks

0 references

Q5002634

0 references

Strongly refuting random CSPs below the spectral threshold

0 references

Identifiers

DOI

10.1088/1742-5468/ac9cc8

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5055432