Fetching the paper…
Reading the bibliography…
We construct and analyze a message-passing algorithm for random constraint satisfaction problems (CSPs) at large clause density, generalizing work of El Alaoui, Montanari, and Sellke for Maximum Cut [arXiv:2111.06813] through a connection between random CSPs and mean-field Ising spin glasses.
Classical and Quantum Bounded Depth Approximation Algorithms, 2019
M. B. Hastings · 1905
Earlier work this paper cites.
Quantum supremacy using a programmable superconducting processor
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, et al · 1910
Earlier work this paper cites.
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou · 1910
Earlier work this paper cites.
Solvable model of a spin-glass
David Sherrington and Scott Kirkpatrick · 1975
Earlier work this paper cites.
Solution of ’solvable model of a spin glass’
David J Thouless, Philip W Anderson, and Robert G Palmer · 1977
Earlier work this paper cites.
Infinite Number of Order Parameters for Spin-Glasses
Giorgio Parisi · 1979
Earlier work this paper cites.
Application of statistical mechanics to NP-complete problems in combinatorial optimisation
Yaotian Fu and Philip W. Anderson · 1986
Earlier work this paper cites.
Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications
Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro · 1987
Earlier work this paper cites.
Probability and Measure
P. Billingsley · 1995
Earlier work this paper cites.
Optimization of mean-field spin glasses, 2020
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke · 2001
Earlier work this paper cites.
Factor graphs and the sum-product algorithm
Frank R Kschischang, Brendan J Frey, and H-A Loeliger · 2001
Earlier work this paper cites.
A CDMA multiuser detection algorithm on the basis of belief propagation
Yoshiyuki Kabashima · 2003
Earlier work this paper cites.
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case, 2020
Edward Farhi, David Gamarnik, and Sam Gutmann · 2004
Earlier work this paper cites.
David Gamarnik, Aukosh Jagannath, and Alexander S. Wein · 2004
Earlier work this paper cites.
Edward Farhi, David Gamarnik, and Sam Gutmann · 2005
Earlier work this paper cites.
The Parisi formula
Michel Talagrand · 2006
Earlier work this paper cites.
Modern Coding Theory
Tom Richardson and Ruediger Urbanke · 2008
Earlier work this paper cites.
Universal Blind Quantum Computation
Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi · 2009
Earlier work this paper cites.
Message-passing algorithms for compressed sensing
David L Donoho, Arian Maleki, and Andrea Montanari · 2009
Earlier work this paper cites.
Probabilistic graphical models: principles and techniques
Daphne Koller and Nir Friedman · 2009
Earlier work this paper cites.
Information, physics, and computation
Marc Mezard and Andrea Montanari · 2009
Earlier work this paper cites.
Optimal transport: old and new
Cédric Villani · 2009
Earlier work this paper cites.
Approximate message passing with spectral initialization for generalized linear models
Marco Mondelli and Ramji Venkataramanan · 2010
Earlier work this paper cites.
MaxCut quantum approximate optimization algorithm performance guarantees for p>1
Jonathan Wurtz and Peter Love · 2010
Earlier work this paper cites.
The dynamics of message passing on dense graphs, with applications to compressed sensing
Mohsen Bayati and Andrea Montanari · 2011
Earlier work this paper cites.
Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
S Yoon, Alexander V Goltsev, Sergey N Dorogovtsev, and JFF Mendes · 2011
Earlier work this paper cites.
Florent Krzakala, Marc Mézard, Francois Sausset, Yifan Sun, and Lenka Zdeborová · 2012
Earlier work this paper cites.
Graphical models concepts in compressed sensing
Andrea Montanari, Yonina C. Eldar, and Gitta Kutyniok · 2012
Earlier work this paper cites.
The computational hardness of counting in two-spin models on d-regular graphs, 2012
Allan Sly and Nike Sun · 2012
Cited alongside, same era.
Quantum computational advantage using photons
Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, et al · 2012
Cited alongside, same era.
Maximum independent sets on random regular graphs, 2013
Jian Ding, Allan Sly, and Nike Sun · 2013
Cited alongside, same era.
The Parisi ultrametricity conjecture
Dmitry Panchenko · 2013
Cited alongside, same era.
The Sherrington-Kirkpatrick Model
Dmitry Panchenko · 2013
Cited alongside, same era.
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke · 2021
Later among the works it cites.
Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou · 2021
Later among the works it cites.
Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs, 2021
Boaz Barak and Kunal Marwaha · 2021
Later among the works it cites.
Sami Boulebnane and Ashley Montanaro · 2021
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
An iterative construction of solutions of the TAP equations for the Sherrington–Kirkpatrick model
Erwin Bolthausen · 2014
Cited alongside, same era.
A quantum approximate optimization algorithm, 2014
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2014
Cited alongside, same era.
Limits of local algorithms over sparse random graphs
David Gamarnik and Madhu Sudan · 2014
Cited alongside, same era.
Beating the random assignment on constraint satisfaction problems of bounded degree, 2015
Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright · 2015
Cited alongside, same era.
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2015
Cited alongside, same era.
A dynamic programming approach to the Parisi functional
Aukosh Jagannath and Ian Tobasco · 2015
Cited alongside, same era.
Parisi formula for the ground state energy in the mixed p-spin model, 2016
Antonio Auffinger and Wei-Kuo Chen · 2016
Cited alongside, same era.
Jian Ding, Allan Sly, and Nike Sun · 2021
Later among the works it cites.
A unifying tutorial on Approximate Message Passing, 2021
Oliver Y. Feng, Ramji Venkataramanan, Cynthia Rush, and Richard J. Samworth · 2021
Later among the works it cites.
The overlap gap property: A topological barrier to optimizing over random structures
David Gamarnik · 2021
Later among the works it cites.
Circuit Lower Bounds for the p-Spin Optimization Problem, 2021
David Gamarnik, Aukosh Jagannath, and Alexander S. Wein · 2021
Later among the works it cites.
Local classical MAX-CUT algorithm outperforms p=2 QAOA on high-girth regular graphs
Kunal Marwaha · 2021
Later among the works it cites.
Optimizing mean field spin glasses with external field, 2021
Mark Sellke · 2021
Later among the works it cites.
Optimization of random high-dimensional functions: Structure and algorithms, 2022
Antonio Auffinger, Andrea Montanari, and Eliran Subag · 2022
Later among the works it cites.
Joao Basso, David Gamarnik, Song Mei, and Leo Zhou · 2022
Later among the works it cites.
Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond, 2022
Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi · 2022
Later among the works it cites.
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end, 2022
Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G. S. L. Brandão · 2022
Later among the works it cites.
Quantum optimization of maximum independent set using Rydberg atom arrays
Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, J-G Liu, Rhine Samajdar, et al · 2022
Later among the works it cites.
Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses, 2022
Brice Huang and Mark Sellke · 2022
Later among the works it cites.
Computational Hardness in Random Optimization Problems from the Overlap Gap Property
Brice Huang · 2022
Later among the works it cites.
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses, 2022
Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, and Jonathan Shi · 2022
Later among the works it cites.
Generalization Analysis of Message Passing Neural Networks on Large Random Graphs, 2022
Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok · 2022
Later among the works it cites.
Dequantizing algorithms to understand quantum advantage in machine learning
Ewin Tang · 2022
Later among the works it cites.
Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
Anurag Anshu and Tony Metger · 2023
Closest in time.
Optimality of Message-Passing Architectures for Sparse Graphs
Aseem Baranwal, Aukosh Jagannath, and Kimon Fountoulakis · 2023
Closest in time.
Wei-Kuo Chen, Dmitry Panchenko, and Eliran Subag · 2023
Closest in time.
David Gamarnik · 2023
Closest in time.
Algorithmic Threshold for Multi-Species Spherical Spin Glasses, 2023
Brice Huang and Mark Sellke · 2023
Closest in time.
Optimization Algorithms for Multi-Species Spherical Spin Glasses, 2023
Brice Huang and Mark Sellke · 2023
Closest in time.
Filip B. Maciejewski, Stuart Hadfield, Benjamin Hall, Mark Hodson, Maxime Dupont, Bram Evert, James Sud, M. Sohaib Alam, Zhihui Wang, Stephen Jeffrey, et al · 2023
Closest in time.
QAOA with N ⋅ p ≥ 200 N\cdot p\geq 200 , 2023
Ruslan Shaydulin and Marco Pistoia · 2023
Closest in time.