Random walks and anO*(n5) volume algorithm for convex bodies
From MaRDI portal
Publication:4350884
DOI<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
László Lovász, 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
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
