Copertina

Algorithmic Universality, Low-Degree Polynomials, and Max-Cut in Sparse Random Graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Cheairi, Houssam El, Gamarnik, David
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Probability 68Q87, 82B44, 60K35
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2
di: Davies, Ewan, et al.
Pubblicazione: (2026)

Critical probabilities for positively associated, finite-range dependent percolation models
di: Köhler-Schindler, Laurin, et al.
Pubblicazione: (2024)

Sharp threshold for network recovery from voter model dynamics
di: Du, Hang, et al.
Pubblicazione: (2025)

On Approximating the Potts Model with Contracting Glauber Dynamics
di: He, Roxanne, et al.
Pubblicazione: (2024)

A study of distributional complexity measures for Boolean functions
di: Köhler-Schindler, Laurin, et al.
Pubblicazione: (2024)

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
di: Li, Zhangsong
Pubblicazione: (2025)

Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs
di: Ding, Jian, et al.
Pubblicazione: (2023)

Metastability of Glauber dynamics with inhomogeneous coupling disorder
di: Bovier, Anton, et al.
Pubblicazione: (2022)

Optimal Hardness of Online Algorithms for Large Independent Sets
di: Gamarnik, David, et al.
Pubblicazione: (2025)

Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
di: Göbel, Andreas, et al.
Pubblicazione: (2025)

The Random Walk Pinning Model I: Lower bounds on the free energy and disorder irrelevance
di: Berger, Quentin, et al.
Pubblicazione: (2025)

The Random Walk Pinning Model II: Upper bounds on the free energy and disorder relevance
di: Berger, Quentin, et al.
Pubblicazione: (2025)

A phase transition and critical phenomenon for the two-dimensional random field Ising model
di: Ding, Jian, et al.
Pubblicazione: (2023)

Random projections beyond zero overlap
di: Wee, Timothy L. H., et al.
Pubblicazione: (2023)

On the large interaction asymptotics of the free energy density of the Ising chain with disordered centered external field
di: Collin, Orphée
Pubblicazione: (2024)

Differentiability of limit shapes in continuous first passage percolation models
di: Bakhtin, Yuri, et al.
Pubblicazione: (2024)

Metastability for the Curie-Weiss-Potts model with unbounded random interactions
di: Dubbeldam, Johan L. A., et al.
Pubblicazione: (2025)

Non-coincidence of critical points for directed polymers on supercritical percolation clusters
di: Cottini, Francesca, et al.
Pubblicazione: (2025)

A Hopf-like formula for mean-field spin glass models
di: Issa, Victor
Pubblicazione: (2024)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
di: Li, Zhangsong
Pubblicazione: (2026)

Strong Disorder for Stochastic Heat Flow and 2D Directed Polymers
di: Berger, Quentin, et al.
Pubblicazione: (2025)

The tail distribution of the partition function for directed polymer in the weak disorder phase
di: Junk, Stefan, et al.
Pubblicazione: (2024)

Characterization of Gradient Condition for Asymmetric Partial Exclusion Processes and Their Scaling Limits
di: Gonçalves, Patrícia, et al.
Pubblicazione: (2024)

Large scale regularity and correlation length for almost length-minimizing random curves in the plane
di: Ried, Tobias, et al.
Pubblicazione: (2024)

Non-constant ground configurations in the disordered ferromagnet
di: Bassan, Michal, et al.
Pubblicazione: (2023)

High moments of 2d directed polymers up to quasi-criticality
di: Cosco, Clément, et al.
Pubblicazione: (2025)

The random field Ising chain domain-wall structure in the large interaction limit
di: Collin, Orphée, et al.
Pubblicazione: (2024)

Disorder Chaos in Short-Range, Diluted, and Lévy Spin Glasses
di: Chen, Wei-Kuo, et al.
Pubblicazione: (2024)

A phase transition for the two-dimensional random field Ising/FK-Ising model
di: Hao, Chenxu, et al.
Pubblicazione: (2025)

The localized phase of pinning models with correlated Gaussian disorder
di: Giacomin, Giambattista, et al.
Pubblicazione: (2026)

A Smooth Computational Transition in Tensor PCA
di: Li, Zhangsong
Pubblicazione: (2025)

A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation
di: Ding, Jian, et al.
Pubblicazione: (2023)

Robust random graph matching in Gaussian models via vector approximate message passing
di: Li, Zhangsong
Pubblicazione: (2024)

Low-temperature Sampling on Sparse Random Graphs
di: Galanis, Andreas, et al.
Pubblicazione: (2025)

Optimal rolling of fair dice using fair coins
di: Huber, Mark, et al.
Pubblicazione: (2024)

Computing the probability of intersection
di: Barvinok, Alexander
Pubblicazione: (2025)

Free energy fluctuations in SK and related spin glass models: A literature survey
di: Collins-Woodfin, Elizabeth, et al.
Pubblicazione: (2025)

Maximum of the Gaussian interface model in random external fields
di: Sakagawa, Hironobu
Pubblicazione: (2023)

Order of fluctuations of the free energy in the positive semi-definite MSK model at critical temperature
di: Collins-Woodfin, Elizabeth, et al.
Pubblicazione: (2025)

Absence of weak disorder for directed polymers on supercritical percolation clusters
di: Nitzschner, Maximilian
Pubblicazione: (2022)