Searching for (sharp) thresholds in random structures: where are we now? (Q6658193)

scientific article; zbMATH DE number 7962923

Language	Label	Description	Also known as
English	Searching for (sharp) thresholds in random structures: where are we now?	scientific article; zbMATH DE number 7962923

Statements

instance of

scholarly article

0 references

title

Searching for (sharp) thresholds in random structures: where are we now? (English)

0 references

author

Will Perkins

0 references

published in

Bulletin of the American Mathematical Society. New Series

0 references

publication date

8 January 2025

0 references

zbMATH Keywords

random constraint satisfaction

0 references

moment methods

0 references

sharp threshold

0 references

MaRDI profile type

Publication

0 references

cites work

Community Detection and Stochastic Block Models

0 references

2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)

0 references

Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster

0 references

On the concentration of the number of solutions of random satisfiability formulas

0 references

Proof of the Achievability Conjectures for the General Stochastic Block Model

0 references

Q4705349

0 references

Almost all graphs with average degree 4 are 3-colorable

0 references

On the 2-colorability of random hypergraphs

0 references

Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold

0 references

The threshold for random k-SAT is 2 k (ln 2 - O(k))

0 references

The probabilistic method

0 references

Critical window of the symmetric perceptron

0 references

Improved bounds for the sunflower lemma

0 references

Avoiding Arrays of Odd Order by Latin Squares

0 references

On the solution of traveling salesman problems

0 references

Storage capacity in symmetric binary perceptrons

0 references

Local entropy as a measure for sampling solutions in constraint satisfaction problems

0 references

On‐line balancing of random inputs

0 references

The condensation phase transition in random graph coloring

0 references

Average-Case Complexity

0 references

Q3682518

0 references

The scaling window of the 2-SAT transition

0 references

Percolation

0 references

Almost all regular graphs are Hamiltonian

0 references

Threshold functions

0 references

Survey propagation: An algorithm for satisfiability

0 references

Testing for high-dimensional geometry in random graphs

0 references

Coloring complete and complete bipartite graphs from random lists

0 references

Solution of a Large-Scale Traveling-Salesman Problem

0 references

Q4228436

0 references

Charting the replica symmetric phase

0 references

Information-theoretic thresholds from the cavity method

0 references

The asymptotic $k$-SAT threshold

0 references

The condensation transition in random hypergraph 2-coloring

0 references

Catching the k-NAESAT threshold

0 references

Enumeration of Seven-Argument Threshold Functions

0 references

High-dimensional random geometric graphs and their clique number

0 references

Maximum independent sets on random regular graphs

0 references

Satisfiability threshold for random regular \textsc{nae-sat}

0 references

Proof of the satisfiability conjecture for large $k$

0 references

Sharp threshold phenomena in statistical physics

0 references

The solution of some random NP-hard problems in polynomial expected time

0 references

Efficient algorithms for discrepancy minimization in convex sets

0 references

On the combinatorial problems which I would most like to see solved

0 references

On the existence of a factor of degree one of a connected random graph

0 references

Q3267900

0 references

Q3286850

0 references

Spanning $F$-cycles in random graphs

0 references

Thresholds versus fractional expectation-thresholds

0 references

Sharp thresholds of graph properties, and the $k$-sat problem

0 references

Hunting for sharp thresholds

0 references

Every monotone graph property has a sharp threshold

0 references

Sharp thresholds for certain Ramsey properties of random graphs

0 references

Introduction to Random Graphs

0 references

Limits of local algorithms over sparse random graphs

0 references

On the Unreasonable Effectiveness of SAT Solvers

0 references

Random Graphs

0 references

Random Plane Networks

0 references

Monotone properties of random geometric graphs have sharp thresholds

0 references

Percolation

0 references

A structure theorem for Boolean functions with small total influences

0 references

Random triangles in random graphs

0 references

The hitting time of clique factors

0 references

Analysing Survey Propagation Guided Decimation on Random Formulas

0 references

Optimal thresholds for Latin squares, Steiner triple systems, and edge colorings

0 references

Q4519896

0 references

Factors in random graphs

0 references

Hitting times for Shamir’s problem

0 references

Asymptotics for Shamir's problem

0 references

Thresholds and Expectation Thresholds

0 references

The threshold for the square of a Hamilton cycle

0 references

Q3597148

0 references

Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor

0 references

Optimal spread for spanning subgraphs of Dirac hypergraphs

0 references

Q3672870

0 references

A Limit Theorem for Multidimensional Galton-Watson Processes

0 references

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

0 references

Covering cubes by random half cubes, with applications to binary neural networks

0 references

Breakdown of a concavity property of mutual information for non-Gaussian channels

0 references

Approximating the unsatisfiability threshold of random formulas

0 references

Limit distribution for the existence of Hamiltonian cycles in a random graph

0 references

Gibbs states and the set of solutions of random constraint satisfaction problems

0 references

Constructive Discrepancy Minimization by Walking on the Edges

0 references

On the threshold problem for Latin boxes

0 references

Community detection thresholds and the weak Ramanujan property

0 references

Threshold Functions for Random Graphs on a Line Segment

0 references

Threshold values of random K‐SAT from the cavity method

0 references

Information, Physics, and Computation

0 references

Q4237477

0 references

Spanning trees in random graphs

0 references

The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness

0 references

Reconstruction and estimation in the planted partition model

0 references

A proof of the block model threshold conjecture

0 references

Noise stability of functions with low influences: invariance and optimality

0 references

Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees

0 references

Analysis of Boolean Functions

0 references

Threshold phenomena for random discrete structures

0 references

A proof of the Kahn–Kalai conjecture

0 references

Random Geometric Graphs

0 references

Frozen 1-RSB structure of the symmetric Ising perceptron

0 references

Sunflowers: from soil to oil

0 references

Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors

0 references

Constructive Discrepancy Minimization for Convex Sets

0 references

Proceedings of the 64th annual IEEE symposium on foundations of computer science, FOCS 2023, Santa Cruz, CA, USA, November 6--9, 2023

0 references

Threshold for Steiner triple systems

0 references

A threshold for perfect matchings in random d-pure hypergraphs

0 references

A smoother notion of spread hypergraphs

0 references

Selector processes on classes of sets

0 references

Are many small sets explicitly small?

0 references

Mean Field Models for Spin Glasses

0 references

Q5421717

0 references

On the critical exponents of random k‐SAT

0 references

Ising model on locally tree-like graphs: uniqueness of solutions to cavity equations

0 references

Identifiers

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6658193