Random generation of combinatorial structures from a uniform distribution

DOI10.1016/0304-3975(86)90174-XzbMath0597.68056OpenAlexW3111890340WikidataQ55967168 ScholiaQ55967168MaRDI QIDQ1079379

Leslie G. Valiant, Vijay V. Vazirani, Mark R. Jerrum

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90174-x

zbMATH Keywords

polynomial hierarchy approximate counting probabilistic Turing machine uniform generation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random number generation in numerical analysis (65C10) Discrete mathematics in relation to computer science (68R99)

Related Items

Robust sub-Gaussian estimation of a mean vector in nearly linear time, On computing minimal independent support and its applications to sampling and counting, Improving the characterization of P-stability for applications in network privacy, Perfect sampling using bounding chains., On approximating weighted sums with exponentially many terms, Counting consistent phylogenetic trees is \#P-complete, On the complexity of interactive proofs with bounded communication, Sequential Monte Carlo for counting vertex covers in general graphs, Estimating the range of a function in an online setting, Counting and sampling $H$-colourings, The computational complexity of calculating partition functions of optimal medians with Hamming distance, Algorithms to approximately count and sample conforming colorings of graphs, Note on the knapsack Markov chain., Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Concentration of the collision estimator, The relative exponential time complexity of approximate counting satisfying assignments, Monte Carlo approximation of form factors with error bounded a priori, Combinatorics of TCP reordering, $\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}$, A quasi-polynomial-time algorithm for sampling words from a context-free language, Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms, Stochastic enumeration method for counting NP-hard problems, On coupling and the approximation of the permanent, Random path method with pivoting for computing permanents of matrices, Approximate counting, uniform generation and rapidly mixing Markov chains, Zeros and approximations of holant polynomials on the complex plane, Algorithmic Pirogov-Sinai theory, Robust statistical learning with Lipschitz and convex loss functions, A sequential algorithm for generating random graphs, Total variation discrepancy of deterministic random walks for ergodic Markov chains, A mildly exponential approximation algorithm for the permanent, On the number of Eulerian orientations of a graph, On the random generation and counting of matchings in dense graphs, Grey-box steganography, Approximate counting in SMT and value estimation for probabilistic programs, The complexity of approximating bounded-degree Boolean $\#$CSP, Rigorous confidence bounds for MCMC under a geometric drift condition, Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs, An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs, Colorful triangle counting and a \textsc{MapReduce} implementation, On the number of occurrences of a symbol in words of regular languages., Sequential importance sampling for multiresolution Kingman-Tajima coalescent counting, Robust machine learning by median-of-means: theory and practice, An inequality for polymatroid functions and its applications., Fast uniform generation of regular graphs, The complexity of approximately counting stable roommate assignments, The complexity of approximately counting stable matchings, Approximating the number of double cut-and-join scenarios, Improved mixing condition on the grid for counting and sampling independent sets, On the complexity of ranking, On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions, On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries, The complexity of controlled selection, Approximating fixation probabilities in the generalized Moran process, On sets polynomially enumerable by iteration, The Ising partition function: zeros and deterministic approximation, Sub-Gaussian estimators of the mean of a random vector, Inapproximability of the Tutte polynomial, Uniform and Bernoulli measures on the boundary of trace monoids, The worm process for the Ising model is rapidly mixing, Dispersion of mass and the complexity of randomized geometric algorithms, Two approximate algorithms for model counting, Normalizing constants of log-concave densities, Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries, Random sampling of colourings of sparse random graphs with a constant number of colours, Stochastic enumeration method for counting trees, On the (im-)possibility of extending coin toss, Approximating the permanent of graphs with large factors, Using TPA to count linear extensions, Solvable integration problems and optimal sample size selection, Bounded-depth circuits cannot sample good codes, An approximation trichotomy for Boolean \#CSP, Learning from MOM's principles: Le Cam's approach, Nearly optimal robust mean estimation via empirical characteristic function, A MOM-based ensemble method for robustness, subsampling and hyperparameter tuning, Iteratively reweighted $\ell_1$-penalized robust regression, Counting and sampling SCJ small parsimony solutions, Approximating the partition function of planar two-state spin systems, Sensitivity analysis of a railway station track layout with respect to a given timetable, Probabilistic complexity classes and lowness, Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems, Spanning tree constrained determinantal point processes are hard to (approximately) evaluate, Counting and sampling minimum $(s,t)$-cuts in weighted planar graphs in polynomial time, Voting power on a graph connected political space with an application to decision-making in the council of the European Union, K-bMOM: A robust Lloyd-type clustering algorithm based on bootstrap median-of-means, Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence, Approximate weighted model integration on DNF structures, An analysis of Monte Carlo algorithm for estimating the permanent, Approximate counting of standard set-valued tableaux, The variational quantum eigensolver: a review of methods and best practices, Uniform generation of NP-witnesses using an NP-oracle, Quantum algorithms for learning Walsh spectra of multi-output Boolean functions, New challenges in covariance estimation: multiple structures and coarse quantization, Planar graph coloring is not self-reducible, assuming P$\neq NP$, Polymer dynamics via cliques: new conditions for approximations, Computational complexity of loss networks, Distribution-free robust linear regression, The complexity of computing maximal word functions, The complexity of estimating min-entropy, ProCount: weighted projected model counting with graded project-join trees, Spatial mixing and the connective constant: optimal bounds, Randomized Reference Models for Temporal Networks, Fast perfect sampling from linear extensions, Analysis on Aggregation Function Spaces, Approximately Counting H-Colourings is $$\#\mathrm {BIS}$$-Hard, Approximate Model Counting via Extension Rule, Constructing SAT Filters with a Quantum Annealer, Sampling colourings of the triangular lattice, Super-polynomial accuracy of one dimensional randomized nets using the median of means, A Graph Polynomial for Independent Sets of Bipartite Graphs, Model Counting of Monotone Conjunctive Normal Form Formulas with Spectra, Approximating the permanent: A simple approach, A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem, Half-regular factorizations of the complete bipartite graph, Unnamed Item, Every finite distributive lattice is isomorphic to the minimizer set of an $M^\natural $-concave set function, On the Complexity of Constrained Determinantal Point Processes, Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle, The Complexity of Approximately Counting Tree Homomorphisms, The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments, On Sampling Simple Paths in Planar Graphs According to Their Lengths, On the expansion of combinatorial polytopes, On languages accepted with simultaneous complexity bounds and their ranking problem, A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph, A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs, On the hardness of approximate reasoning, Faster FPTASes for counting and random generation of knapsack solutions, Unnamed Item, Unnamed Item, Mean estimation with sub-Gaussian rates in polynomial time, A complexity classification of spin systems with an external field, Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting), Robust classification via MOM minimization, Unnamed Item, Fast convergence of the Glauber dynamics for sampling independent sets, Nonasymptotic bounds on the estimation error of MCMC algorithms, Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor, A Markov chain on the solution space of edge colorings of bipartite graphs, Some Problems on Approximate Counting in Graphs and Matroids, How to get more mileage from randomness extractors, Computing and counting longest paths on circular-arc graphs in polynomial time, Knowledge-based programs, Rényi entropies as a measure of the complexity of counting problems, Computing Scores of Forwarding Schemes in Switched Networks with Probabilistic Faults, Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas, The Potts model and the Tutte polynomial, Self-testing algorithms for self-avoiding walks, New collapse consequences of NP having small circuits, On enumerating minimal dicuts and strongly connected subgraphs, Proving SAT does not have small circuits with an application to the two queries problem, Lee-Yang theorems and the complexity of computing averages, Probabilistic verification and approximation, Random bichromatic matchings, Counting subsets of contingency tables, Lower bounds for non-black-box zero knowledge, Simulated annealing in convex bodies and an $O^{*}(n^{4}$) volume algorithm, Uniform generation in spatial constraint databases and applications, Unnamed Item, Unnamed Item, Unnamed Item, Exponential Time Complexity of Weighted Counting of Independent Sets, Distributed statistical estimation and rates of convergence in normal approximation, Identity-Based Hierarchical Key-Insulated Encryption Without Random Oracles, Random k -noncrossing RNA structures, Deterministic and randomized polynomial‐time approximation of radii, Sampling and Counting 3-Orientations of Planar Triangulations, Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard, Halving the Bounds for the Markov, Chebyshev, and Chernoff Inequalities Using Smoothing, High-confidence estimation of small s -t reliabilities in directed acyclic networks, In a World of P=BPP, Optimal confidence for Monte Carlo integration of smooth functions, Strong Spatial Mixing and Rapid Mixing with Five Colours for the Kagome Lattice, Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction, Generation of solved instances of Multiconstraint Knapsack problem and its applications to Private Key Cipher, Solving and sampling with many solutions, Approximability of the eight-vertex model, Quantum Chebyshev's Inequality and Applications, Unnamed Item, The breakdown point of the median of means tournament, Proper learning of $k$-term DNF formulas from satisfying assignments, Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time, Deterministic counting of graph colourings using sequences of subgraphs, Frozen (Δ + 1)-colourings of bounded degree graphs, Simulation reductions for the Ising model, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, Counting Weighted Independent Sets beyond the Permanent, Solving and sampling with many solutions: Satisfiability and other hard problems, Mean estimation and regression under heavy-tailed distributions: A survey, Unnamed Item, Randomly coloring constant degree graphs, Near-optimal mean estimators with respect to general norms, Unnamed Item, Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z², Sequential stratified splitting for efficient Monte Carlo integration, Heat flow and a faster algorithm to compute the surface area of a convex body, On the effective generation of set elements within specified ranges, Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs, Random Generation for Finitely Ambiguous Context-free Languages, Improved inapproximability results for counting independent sets in the hard-core model, Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs, Exponential inequalities for unbounded functions of geometrically ergodic Markov chains: applications to quantitative error bounds for regenerative Metropolis algorithms, Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction, Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers, Fixed Precision MCMC Estimation by Median of Products of Averages, On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries, Nonasymptotic Bounds on the Mean Square Error for MCMC Estimates via Renewal Techniques, Counting vertices of integral polytopes defined by facets, Perfect sampling from spatial mixing, Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields, Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture, Bijecting hidden symmetries for skew staircase shapes, Non-asymptotic analysis and inference for an outlyingness induced winsorized mean, Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation, (Nondeterministic) hardness vs. non-malleability, Sequential importance sampling for estimating expectations over the space of perfect matchings, Algorithms for hard-constraint point processes via discretization, Counting cycles on planar graphs in subexponential time, Inapproximability of counting independent sets in linear hypergraphs, Finite sample complexity of sequential Monte Carlo estimators on multimodal target distributions, Approximately counting and sampling knowledge states, Exact distributed sampling, Counting cycles on planar graphs in subexponential time, Robust supervised learning with coordinate gradient descent, Finite-sample complexity of sequential Monte Carlo estimators, Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid, Models of random subtrees of a graph, Nowhere to go but high: a perspective on high-dimensional expanders, Interactions of computational complexity theory and mathematics, Mean estimation in high dimension, Beyond windability: approximability of the four-vertex model, ANALYSIS OF QUANTUM FUNCTIONS, Generalized loop‐erased random walks and approximate reachability, Random Construction of Interpolating Sets for High-Dimensional Integration, Counting by quantum eigenvalue estimation, Counting independent sets in graphs with bounded bipartite pathwidth, On the computational power of DNA, A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant, Graph classes and the switch Markov chain for matchings, Approximately Counting Embeddings into Random Graphs, Generating all vertices of a polyhedron is hard, Reconfiguration of connected graph partitions via recombination, Counting Perfect Matchings and the Switch Chain, Reconfiguration of connected graph partitions via recombination, Counting Hypergraph Colorings in the Local Lemma Regime, Approximate Counting via Correlation Decay in Spin Systems, Dynamic Sampling from Graphical Models

Cites Work