Cover Image

Belief Propagation Guided Decimation on Random k-XORSAT

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chatterjee, Arnab, Coja-Oghlan, Amin, Kang, Mihyun, Krieg, Lena, Rolvien, Maurice, Sorkin, Gregory B.
Format:	Preprint
Published:	2025
Subjects:	Combinatorics Discrete Mathematics 60B20, 68W20
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Symmetric Rule-Based Achlioptas Processes for Random $k$-SAT
by: Chatterjee, Arnab
Published: (2025)

The random $k$-SAT Gibbs uniqueness threshold revisited
by: Chatterjee, Arnab, et al.
Published: (2025)

The rank of sparse random matrices
by: Coja-Oghlan, Amin, et al.
Published: (2019)

Asymptotic size of the Karp-Sipser Core in Configuration Model
by: Chatterjee, Arnab, et al.
Published: (2025)

On sampling two spin models using the local connective constant
by: Efthymiou, Charilaos
Published: (2024)

On sampling diluted Spin-Glasses with unbounded interactions
by: Efthymiou, Charilaos, et al.
Published: (2026)

An Improved Drift Theorem for Balanced Allocations
by: Los, Dimitrios, et al.
Published: (2023)

Algebraic Algorithms for Fractional Linear Matroid Parity via Non-commutative Rank
by: Oki, Taihei, et al.
Published: (2022)

On the Parenthesisations of Matrix Chains: All are Useful, Few Are Essential
by: López, Francisco, et al.
Published: (2023)

Noisy group testing via spatial coupling
by: Coja-Oghlan, Amin, et al.
Published: (2024)

Incremental-Decremental Maximization
by: Disser, Yann, et al.
Published: (2025)

On sampling symmetric Gibbs distributions on sparse random graphs and hypergraphs
by: Efthymiou, Charilaos
Published: (2020)

On Subsample Size of Quantile-Based Randomized Kaczmarz
by: Cai, Jian-Feng, et al.
Published: (2025)

WalkSAT is linear on random 2-SAT
by: Berenbrink, Petra, et al.
Published: (2024)

An asymptotically optimal algorithm for generating bin cardinalities
by: Devroye, Luc, et al.
Published: (2024)

The Power of Filling in Balanced Allocations
by: Los, Dimitrios, et al.
Published: (2022)

Mean-Biased Processes for Balanced Allocations
by: Los, Dimitrios, et al.
Published: (2023)

Fundamentals of Partial Rejection Sampling
by: Jerrum, Mark
Published: (2021)

A new look at perfect simulation for chains with infinite memory
by: De Santis, Emilio, et al.
Published: (2025)

The degree-restricted random process is far from uniform
by: Molloy, Michael, et al.
Published: (2022)

Analysis of d-ary Tree Algorithms with Successive Interference Cancellation
by: Vogel, Quirin, et al.
Published: (2023)

Algorithms for Generating Small Random Samples
by: Cicirello, Vincent A.
Published: (2024)

Convergence of Markov Chains for Constant Step-size Stochastic Gradient Descent with Separable Functions
by: Shirokoff, David, et al.
Published: (2024)

Bad local minima exist in the stochastic block model
by: Coja-Oghlan, Amin, et al.
Published: (2024)

The number of random 2-SAT solutions is asymptotically log-normal
by: Chatterjee, Arnab, et al.
Published: (2024)

Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
by: Feldman, Moran, et al.
Published: (2026)

Finding cliques and dense subgraphs using edge queries
by: Csóka, Endre, et al.
Published: (2023)

Random Source Iteration Method: Mitigating the Ray Effect in the Discrete Ordinates Method
by: Fu, Jingyi, et al.
Published: (2025)

Randomized block-Krylov subspace methods for low-rank approximation of matrix functions
by: Persson, David, et al.
Published: (2025)

Random-Order Online Independent Set of Intervals and Hyperrectangles
by: Garg, Mohit, et al.
Published: (2024)

Dirac's theorem and the switch geometry of perfect matchings
by: Kang, Ross J., et al.
Published: (2026)

Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning
by: Rokhlin, Dmitry B., et al.
Published: (2025)

Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds
by: Opris, Andre
Published: (2025)

Time-Biased Random Walks and Robustness of Expanders
by: Olesker-Taylor, Sam, et al.
Published: (2024)

Accelerating a restarted Krylov method for matrix functions with randomization
by: Guidotti, Nicolas L., et al.
Published: (2025)

Beyond Low Rank: Fast Low-Rank + Diagonal Decomposition with a Spectral Approach
by: Yeon, Kingsley, et al.
Published: (2025)

Algorithms for the ferromagnetic Potts model on expanders
by: Carlson, Charlie, et al.
Published: (2022)

Matrix-free stochastic calculation of operator norms without using adjoints
by: Bresch, Jonas, et al.
Published: (2024)

A Mini-Batch Method for Solving Nonlinear PDEs with Gaussian Processes
by: Yang, Xianjin, et al.
Published: (2023)

A Simulation of Optimal Dryness When Moving in the Rain or Snow Using MATLAB
by: Zhao, Neil, et al.
Published: (2024)