Random walks and anO*(n5) volume algorithm for convex bodies
From MaRDI portal
Publication:4350884
DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X" /><1::AID-RSA1>3.0.CO;2-X 10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-XzbMath0895.60075OpenAlexW2041990574MaRDI QIDQ4350884
Miklós Simmonovits, Ravindran Kannan
Publication date: 4 September 1997
Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199708)11:1<1::aid-rsa1>3.0.co;2-x
Sums of independent random variables; random walks (60G50) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)
Related Items (75)
Random walks on finite nilpotent groups driven by long-jump measures ⋮ Randomly coloring simple hypergraphs with fewer colors ⋮ On the mixing time of coordinate Hit-and-Run ⋮ Practical Volume Estimation of Zonotopes by a New Annealing Schedule for Cooling Convex Bodies ⋮ Optimal outlier removal in high-dimensional spaces ⋮ A practical volume algorithm ⋮ Sampling discretization and related problems ⋮ A parallel implementation of an \(O^\ast(n^4)\) volume algorithm ⋮ Entanglement in bipartite quantum systems: Euclidean volume ratios and detectability by Bell inequalities ⋮ Concentration phenomena in high dimensional geometry ⋮ A Fast and Practical Method to Estimate Volumes of Convex Polytopes ⋮ Efficient sampling in spectrahedra and volume approximation ⋮ On the computational complexity of MCMC-based estimators in large samples ⋮ Simulated annealing for convex optimization: rigorous complexity analysis and practical perspectives ⋮ \(L_{p}\)-moments of random vectors via majorizing measures ⋮ Coupling with the stationary distribution and improved sampling for colorings and independent sets ⋮ Geodesic Walks in Polytopes ⋮ Faster mixing and small bottlenecks ⋮ Computing and estimating the volume of the solution space of SMT(LA) constraints ⋮ Complexity Analysis of a Sampling-Based Interior Point Method for Convex Optimization ⋮ Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume ⋮ Empirical processes with a bounded \(\psi_1\) diameter ⋮ Covariance estimation for distributions with \({2+\varepsilon}\) moments ⋮ Meta-control of an interacting-particle algorithm for global optimization ⋮ On singular values of matrices with independent rows ⋮ The Swendsen–Wang dynamics on trees ⋮ Fuzzy ranking of human development: a proposal ⋮ Geometric and functional inequalities for log-concave probability sequences ⋮ Sharp bounds on the rate of convergence of the empirical covariance matrix ⋮ John’s walk ⋮ Computational results of an \(O^{\ast }(n^{4})\) volume algorithm ⋮ An algorithm for estimating non-convex volumes and other integrals in \(n\) dimensions ⋮ Convergence of Gibbs sampling: coordinate hit-and-run mixes fast ⋮ Finite-sample complexity of sequential Monte Carlo estimators ⋮ Randomly coloring simple hypergraphs ⋮ Unnamed Item ⋮ Geometry of log-concave ensembles of random matrices and approximate reconstruction ⋮ Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions ⋮ Mixing times for uniformly ergodic Markov chains ⋮ On the conditioning of random subdictionaries ⋮ On approximation by projections of polytopes with few facets ⋮ Approximating fixed points of weakly contracting mappings ⋮ Log-concavity and strong log-concavity: a review ⋮ Dispersion of mass and the complexity of randomized geometric algorithms ⋮ On weakly bounded empirical processes ⋮ Uniformly Generating Origin Destination Tables ⋮ Near-optimal deterministic algorithms for volume computation via M-ellipsoids ⋮ What is the complexity of volume calculation? ⋮ Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles ⋮ Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm ⋮ Uniform generation in spatial constraint databases and applications ⋮ A probabilistic approach to the geometry of the \(\ell^n_p\)-ball ⋮ Approximating the volume of unions and intersections of high-dimensional geometric objects ⋮ Unnamed Item ⋮ How close is the sample covariance matrix to the actual covariance matrix? ⋮ Mixing time of an unaligned Gibbs sampler on the square ⋮ Approximating the moments of marginals of high-dimensional distributions ⋮ Spectral norm of products of random and deterministic matrices ⋮ A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant ⋮ Generating a random collection of discrete joint probability distributions subject to partial information ⋮ Asymptotic shape of a random polytope in a convex body ⋮ High-dimensional nonparametric density estimation via symmetry and shape constraints ⋮ Deterministic and randomized polynomial‐time approximation of radii ⋮ Approximation of convex sets by polytopes ⋮ Question selection for multi-attribute decision-aiding. ⋮ Complexity of approximating the vertex centroid of a polyhedron ⋮ Optimization of a convex program with a polynomial perturbation ⋮ Approximate weighted model integration on DNF structures ⋮ Random vectors in the isotropic position ⋮ Some remarks about the maximal perimeter of convex sets with respect to probability measures ⋮ Randomly coloring constant degree graphs ⋮ Sampling convex bodies: a random matrix approach ⋮ Estimating the volume of solution space for satisfiability modulo linear real arithmetic ⋮ Similarity of personal preferences: Theoretical foundations and empirical analysis ⋮ Randomized interior point methods for sampling and optimization
This page was built for publication: Random walks and anO*(n5) volume algorithm for convex bodies
