The solution of some random NP-hard problems in polynomial expected time
From MaRDI portal
Recommendations
Cited in
(51)- Average polynomial time complexity of some NP-complete problems
- Expected complexity of graph partitioning problems
- Probabilistic hyperedge replacement grammars
- The Metropolis algorithm for graph bisection
- Contiguity and non-reconstruction results for planted partition models: the dense case
- Deciding \(k\)-colorability in expected polynomial time
- A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms
- Consistent nonparametric estimation for heavy-tailed sparse graphs
- Step-by-step community detection in volume-regular graphs
- Exact recovery in the Ising blockmodel
- Distributed community detection in dynamic graphs
- Refining the phase transition in combinatorial search
- Algorithms for graph partitioning on the planted partition model
- An expected polynomial time algorithm for coloring 2-colorable 3-graphs
- Distributed Community Detection in Dynamic Graphs
- A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems
- Disentangling group and link persistence in dynamic stochastic block models
- Solving NP-hard semirandom graph problems in polynomial expected time
- Random instances of problems in NP -- algorithms and statistical physics
- Graph partitioning via adaptive spectral techniques
- RANDOMIZATION YIELDS SIMPLE O(n log⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
- scientific article; zbMATH DE number 1107723 (Why is no real title available?)
- Community detection and stochastic block models: recent developments
- Asymptotic mutual information for the balanced binary stochastic block model
- Reconstruction and estimation in the planted partition model
- The replica symmetric phase of random constraint satisfaction problems
- Coloring random graphs
- Joint community detection and rotational synchronization via semidefinite programming
- New abilities and limitations of spectral graph bisection
- Find Your Place: Simple Distributed Algorithms for Community Detection
- Families with infants: a general approach to solve hard partition problems
- Branch-and-bound solves random binary IPs in poly(n)-time
- Combinatorial statistics and the sciences
- Coloring k-colorable graphs in constant expected parallel time
- Mutual information for the sparse stochastic block model
- A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
- Asymptotic uncertainty quantification for communities in sparse planted bi-section models
- Learning sparse graphons and the generalized Kesten-Stigum threshold
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Near-optimal dominating sets in dense random graphs in polynomial expected time
- A hard problem that is almost always easy
- Model-Based Clustering of Nonparametric Weighted Networks With Application to Water Pollution Analysis
- Searching for (sharp) thresholds in random structures: where are we now?
- Confidence sets in a sparse stochastic block model with two communities of unknown sizes
- Exact recovery of community detection in k-community Gaussian mixture models
- Exact recovery discrimination in planted bisection model
- Exact phase transitions for stochastic block models and reconstruction on trees
- A fast coloring oracle for average case hypergraphs
- Community detection in sparse networks via Grothendieck's inequality
- Complexity analysis of a decentralised graph colouring algorithm
- Why almost all k-colorable graphs are easy to color
This page was built for publication: The solution of some random NP-hard problems in polynomial expected time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3031922)
