Simulated annealing in convex bodies and an O*(n4) volume algorithm

No abstract is available for this paper.

• Publication year

  2006

• Venue

  Journal of computer and system sciences (Print)

• Publication date

  2006-03-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.jcss.2005.08.004
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Solving convex programs by random walks

  2004cited by this paper
• Hit-and-run from a corner

  2004influential reference
• Logconcave functions: geometry and efficient sampling algorithms

  2003cited by this paper
• The Geometry of Logconcave Functions and Sampling Algorithms ∗

  2003cited by this paper
• Hit-and-Run is Fast and Fun 1

  2003cited by this paper
• The Geometry of Logconcave Functions and an O* (n 3 ) Sampling Algorithm

  2003cited by this paper
• Where to Start a Geometric Random Walk

  2003cited by this paper
• Random Points in Isotropic Convex Sets

  1998cited by this paper
• Random walks and an O * ( n 5 ) volume algorithm for convex bodies

  1997cited by this paper
• Random walks and an O*(n5) volume algorithm for convex bodies

  1997cited by this paper
• Random Vectors in the Isotropic Position

  1996cited by this paper
• Isoperimetric problems for convex bodies and a localization lemma

  1995cited by this paper
• Random Walks in a Convex Body and an Improved Volume Algorithm

  1993cited by this paper
• On the randomized complexity of volume and diameter

  1992cited by this paper
• Computing the volume of convex bodies : a case where randomness provably helps

  1991cited by this paper
• Sampling and integration of near log-concave functions

  1991cited by this paper
• The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume

  1990cited by this paper
• A random polynomial time algorithm for approximating the volume of convex bodies

  1989cited by this paper
• Computing the volume is difficult

  1986cited by this paper
• A geometric inequality and the complexity of computing volume

  1986cited by this paper
• Random Generation of Combinatorial Structures from a Uniform Distribution

  1986cited by this paper
• Optimization by Simulated Annealing

  1983cited by this paper
• On logarithmic concave measures and functions

  1973cited by this paper
• On a Certain Converse of Hölder’s Inequality

  1972cited by this paper
• Logarithmic concave measures with applications to stochastic programming

  1971cited by this paper
• Über eine Klasse superadditiver Mengenfunktionale von Brunn-Minkowski-Lusternikschem Typus

  1957cited by this paper

• Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs

  2026cites this paper
• Efficient Volume Computation for SMT Formulas

  2025cites this paper
• Computing Asymptotic Bounds for Small Roots in Coppersmith's Method via Sumset Theory

  2025cites this paper
• Quantum Circuits for the Metropolis-Hastings Algorithm

  2025cites this paper
• Mixed Cayley and Cartesian sampling for fast and accurate coverage and configurational entropy computation

  2025cites this paper
• Tukey Depth Mechanisms for Practical Private Mean Estimation

  2025cites this paper
• Sampling and Integration of Logconcave Functions by Algorithmic Diffusion

  2024cites this paper
• Maximizing Slice-Volumes of Semialgebraic Sets using Sum-of-Squares Programming

  2024cites this paper
• Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games

  2024cites this paper
• An adaptive simulated annealing-based computational offloading scheme in UAV-assisted MEC networks

  2024cites this paper
• On Efficient Approximation of the Maximum Distance to A Point Over an Intersection of Balls

  2024cites this paper
• dingo: a Python package for metabolic flux sampling

  2023cites this paper
• Query lower bounds for log-concave sampling

  2023cites this paper
• The Mathematics of L\'aszl\'o Lov\'asz

  2023cites this paper
• Projection-Free Online Convex Optimization via Efficient Newton Iterations

  2023cites this paper
• A Practical Algorithm for Volume Estimation based on Billiard Trajectories and Simulated Annealing

  2023influential citation
• A parallel implementation of an O ∗ ( n 4 ) volume algorithm. (English)

  2022cites this paper
• Quasi-Newton Steps for Efficient Online Exp-Concave Optimization

  2022cites this paper
• Sampling from Convex Sets with a Cold Start using Multiscale Decompositions

  2022cites this paper
• Probabilistic Analysis of Network Availability

  2022cites this paper
• Floating bodies and approximation of convex bodies by polytopes

  2022cites this paper
• Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptions

  2022cites this paper
• Efficient sampling in spectrahedra and volume approximation

  2022cites this paper
• Gaussian Perturbations in ReLU Networks and the Arrangement of Activation Regions

  2022cites this paper
• Simulated Annealing for Convex Optimization: Rigorous Complexity Analysis and Practical Perspectives

  2022influential citation
• Randomized geometric tools for anomaly detection in stock markets

  2022cites this paper
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions

  2022cites this paper
• Hit-and-run mixing via localization schemes

  2022cites this paper
• Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods

  2022cites this paper
• Efficient computation of the volume of a polytope in high-dimensions using Piecewise Deterministic Markov Processes

  2022cites this paper
• Deterministic Approximation Algorithms for Volumes of Spectrahedra

  2022cites this paper
• Sampling Matrices From Harish‐Chandra–Itzykson–Zuber Densities With Applications to Quantum Inference and Differential Privacy

  2021cites this paper
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: Continuous dynamics

  2021cites this paper
• Covariance-Aware Private Mean Estimation Without Private Covariance Estimation

  2021cites this paper
• Probabilistic Stability Assessment for Active Distribution Grids

  2021cites this paper
• A Novel Data Analytics Method for Predicting the Delivery Speed of Software Enhancement Projects

  2020cites this paper
• Improved polytope volume calculations based on Hamiltonian Monte Carlo with boundary reflections and sweet arithmetics

  2020cites this paper
• Sampling the feasible sets of SDPs and volume approximation

  2020cites this paper
• Geometric Algorithms for Sampling the Flux Space of Metabolic Networks

  2020cites this paper
• CGWeek Young Researchers Forum 2020

  2020cites this paper
• Reducing isotropy and volume to KLS: an o*(n3ψ2) volume algorithm

  2020influential citation
• Strongly Convex Divergences

  2020cites this paper
• volesti: Volume Approximation and Sampling for Convex Polytopes in R

  2020cites this paper
• Mathematical Software – ICMS 2020: 7th International Conference, Braunschweig, Germany, July 13–16, 2020, Proceedings

  2020cites this paper
• Practical Volume Estimation of Zonotopes by a New Annealing Schedule for Cooling Convex Bodies

  2020cites this paper
• Tangent Space Sensitivity and Distribution of Linear Regions in ReLU Networks

  2020cites this paper
• Structured Logconcave Sampling with a Restricted Gaussian Oracle

  2020cites this paper
• How to Find a Point in the Convex Hull Privately

  2020influential citation
• Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast

  2020cites this paper
• On the Approximability of Weighted Model Integration on DNF Structures

  2020influential citation
• Efficient Sampling from Feasible Sets of SDPs and Volume Approximation

  2020cites this paper
• Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms

  2020cites this paper
• On the mixing time of coordinate Hit-and-Run

  2020cites this paper
• Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases

  2020cites this paper
• Improved analysis of higher order random walks and applications

  2020cites this paper
• The gradient complexity of linear regression

  2019cites this paper
• Strong self-concordance and sampling

  2019cites this paper
• Theory and Applications of Models of Computation: 15th Annual Conference, TAMC 2019, Kitakyushu, Japan, April 13–16, 2019, Proceedings

  2019cites this paper
• A Probabilistic Method for Pruning CADJ Graphs with Applications to SOM Clustering

  2019cites this paper
• Estimating normalizing constants for log-concave distributions: algorithms and lower bounds

  2019cites this paper
• Practical Volume Estimation by a New Annealing Schedule for Cooling Convex Bodies

  2019cites this paper
• Optimal estimation in high-dimensional and nonparametric models

  2019cites this paper
• Simulating sticky particles: A Monte Carlo method to sample a Stratification

  2019influential citation
• Faster algorithms for polytope rounding, sampling, and volume computation via a sublinear "Ball Walk"

  2019influential citation
• The Volume of a Crosspolytope Truncated by a Halfspace

  2019cites this paper
• Simulated annealing with hit-and-run for convex optimization: rigorous complexity analysis and practical perspectives for copositive programming

  2019influential citation
• Semidefinite Relaxations for Lebesgue and Gaussian Measures of Unions of Basic Semialgebraic Sets

  2019cites this paper
• Faster Polytope Rounding, Sampling, and Volume Computation via a Sub-Linear Ball Walk

  2019influential citation
• On Geometric Structure of Activation Spaces in Neural Networks

  2019cites this paper
• Quantum Algorithm for Estimating Volumes of Convex Bodies

  2019influential citation
• Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature

  2019influential citation
• The Distribution Function of the Longest Path Length in Constant Treewidth DAGs with Random Edge Length

  2019cites this paper
• A practical algorithm for volume estimation based on billiard trajectories and simulated annealing

  2019cites this paper
• The Randomized Midpoint Method for Log-Concave Sampling

  2019cites this paper
• Random walks for estimating densities of states and the volume of convex bodies in high dimensional spaces. (Marches aléatoires pour l'estimation de densités d'états et de volume de convexes en grande dimension)

  2019cites this paper
• A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families

  2019cites this paper
• Practical Polytope Volume Approximation

  2018influential citation
• Complexity Analysis of a Sampling-Based Interior Point Method for Convex Optimization

  2018influential citation
• The Kannan-Lovász-Simonovits Conjecture

  2018influential citation
• Hamiltonian Monte Carlo with boundary reflections, and application to polytope volume calculations

  2018cites this paper
• Online Newton Step Algorithm with Estimated Gradient

  2018cites this paper
• A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities

  2018cites this paper
• An optimization framework to combine operable space maximization with design of experiments

  2018cites this paper
• The Kannan-Lov\'asz-Simonovits Conjecture.

  2018influential citation
• Polytope Membership in High Dimension

  2018cites this paper
• The Soft Multivariate Truncated Normal Distribution with Applications to Bayesian Constrained Estimation

  2018cites this paper
• Algorithms for Deciding Membership in Polytopes of General Dimension

  2018cites this paper
• Optimization Everywhere: Convex, Combinatorial, and Economic

  2018cites this paper
• Finite Sample Complexity of Sequential Monte Carlo Estimators

  2018influential citation
• The Soft Multivariate Truncated Normal Distribution

  2018cites this paper
• From Quantum Gravity to Combinatorial Hives: Addressing Longstanding Puzzles with Novel Approaches

  2018cites this paper
• An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths

  2017cites this paper
• CHRR: coordinate hit-and-run with rounding for uniform sampling of constraint-based models

  2017cites this paper
• Lebesgue and gaussian measure of unions of basic semi-algebraic sets

  2017cites this paper
• Mixing time of an unaligned Gibbs sampler on the square

  2017cites this paper
• Fast MCMC Sampling Algorithms on Polytopes

  2017cites this paper
• A Bernoulli mean estimate with known relative error distribution

  2017cites this paper
• Lp-Adaptation: Simultaneous Design Centering and Robustness Estimation of Electronic and Biological Systems

  2017cites this paper
• Geometric Methods for Robust Data Analysis in High Dimension

  2017cites this paper
• Honey from the Hives: A Theoretical and Computational Exploration of Combinatorial Hives

  2017cites this paper