scientific article; zbMATH DE number 420886

zbMATH Open0780.68096MaRDI QIDQ3135094FDOQ3135094

Authors: Alistair Sinclair 

Publication date: 22 September 1993

Title of this publication is not available (Why is that?)

Recommendations

• Approximate counting, uniform generation and rapidly mixing Markov chains
• scientific article; zbMATH DE number 1789923
• Approximating the Permanent
• scientific article; zbMATH DE number 1885142
• scientific article; zbMATH DE number 1342087

zbMATH Keywords

simulationMarkov chainsconductancepermanentscombinatorial structuresrapid mixing

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Probabilistic methods, stochastic differential equations (65C99) Computational methods for sparse matrices (65F50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Combinatorics in computer science (68R05) Determinants, permanents, traces, other special matrix functions (15A15)

Cited In (only showing first 100 items - show all)

• A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search
• Random Generation of Directed Acyclic Graphs
• Expander properties and the cover time of random intersection graphs
• Mixing times for uniformly ergodic Markov chains
• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Title not available (Why is that?)
• Randomized scheduling algorithm for queueing networks
• The complexity of estimating min-entropy
• Revlex-initial 0/1-polytopes
• Analysis of a nonreversible Markov chain sampler.
• The hitting and cover times of Metropolis walks
• The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule
• Phase transitions in random dyadic tilings and rectangular dissections
• On listing, sampling, and counting the chordal graphs with edge constraints
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• Tight bounds for the cover time of multiple random walks
• Fast convergence of the Glauber dynamics for sampling independent sets
• Similarity of personal preferences: Theoretical foundations and empirical analysis
• On coupling and the approximation of the permanent
• Mixing time for the Ising model: a uniform lower bound for all graphs
• On the hardness of sampling independent sets beyond the tree threshold
• Gröbner bases and triangulations of the second hypersimplex
• Mixing times for the swapping algorithm on the Blume-Emery-Griffiths model
• Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
• Pattern hit-and-run for sampling efficiently on polytopes
• Approximating the number of monomer-dimer coverings of a lattice.
• Algorithms to approximately count and sample conforming colorings of graphs
• Optimal search-relocation trade-off in Markovian-target searching
• Evolving sets, mixing and heat kernel bounds
• Title not available (Why is that?)
• Expansion of random graphs: new proofs, new results
• Coined quantum walks lift the cospectrality of graphs and trees
• Approximate counting, uniform generation and rapidly mixing Markov chains
• The computational complexity of estimating MCMC convergence time
• Deterministic random walks on finite graphs
• Phase coexistence and torpid mixing in the 3-coloring model on \({\mathbb Z}^d\)
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• The swapping algorithm for the Hopfield model with two patterns
• Algorithms for Generating Discrete Random Variables with a Given Generating Function or a Given Moment Sequence
• Probabilistic verification and approximation
• On the swapping algorithm
• Markov chain decomposition for convergence rate analysis
• Effect of increasing the energy gap between the two lowest energy states on the mixing time of the Metropolis algorithm
• The algorithmics of folding proteins on lattices.
• Disjoint Decomposition of Markov Chains and Sampling Circuits in Cayley Graphs
• Nash inequalities for finite Markov chains
• Uniform positivity improving property, Sobolev inequalities, and spectral gaps
• Importance sampling for families of distributions
• Eigenvalues, inequalities and ergodic theory
• Rapid mixing for lattice colourings with fewer colours
• Markov-chain monte carlo: Some practical implications of theoretical results
• Tilings of rectangles with T-tetrominoes
• Numerical study of the 6-vertex model with domain wall boundary conditions.
• Algebraic algorithms for sampling from conditional distributions
• A mildly exponential approximation algorithm for the permanent
• Uniform generation of NP-witnesses using an NP-oracle
• Perfect sampling using bounding chains.
• Stochastic protein folding simulation in the three-dimensional HP-model
• The Markov chain of colourings
• The Markov chain Monte Carlo revolution
• Efficient importance sampling for binary contingency tables
• Perfect Simulation for Image Restoration
• Graph clustering
• Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison
• What do we know about the Metropolis algorithm?
• Walks on generating sets of Abelian groups
• On swapping and simulated tempering algorithms.
• Generating connected acyclic digraphs uniformly at random
• Logarithmic Sobolev inequalities for finite Markov chains
• Uniform sampling of digraphs with a fixed degree sequence
• Title not available (Why is that?)
• Analyzing Glauber dynamics by comparison of Markov chains
• Identification of almost invariant aggregates in reversible nearly uncoupled Markov chains
• An interruptible algorithm for perfect sampling via Markov chains
• Sampling and counting 3-orientations of planar triangulations
• A quasi-polynomial-time algorithm for sampling words from a context-free language
• Relation-algebraic computation of fixed points with applications
• Distributed cooperative Bayesian learning strategies.
• Leader election in well-connected graphs
• The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processors
• Sex: the power of randomization
• Reverse cycle walking and its applications
• Utilizing network structure to accelerate Markov chain Monte Carlo algorithms
• Title not available (Why is that?)
• How to Design a Linear Cover Time Random Walk on a Finite Graph
• Simple polytopes without small separators. II: Thurston's bound
• Fastest mixing Markov chain problem for the union of two cliques
• Rapid mixing and Markov bases
• Rumor spreading with no dependence on conductance
• Exploration of NP-hard enumeration problems by simulated annealing -- the spectrum values of permanents
• On the random generation and counting of matchings in dense graphs
• Mixing times of Markov chains for self‐organizing lists and biased permutations
• Deterministic random walks for rapidly mixing chains
• Combinatiorial Markov chains
• Sequential importance sampling for multiresolution Kingman-Tajima coalescent counting
• Half-graphs, other non-stable degree sequences, and the switch Markov chain
• Approximately sampling elements with fixed rank in graded posets
• Generating random networks without short cycles
• The ‘Burnside Process’ Converges Slowly

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3135094)