Source author record

Ben Cousins

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.FA Computational Complexity math.PR

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A near-optimal algorithm for approximating the John Ellipsoid

We develop a simple and efficient algorithm for approximating the John Ellipsoid of a symmetric polytope. Our algorithm is near optimal in the sense that our time complexity matches the current best verification algorithm. We also provide the MATLAB code for further research.

preprint2016arXiv

Gaussian Cooling and O*(n^3) Algorithms for Volume and Gaussian Volume

We present an $O^*(n^3)$ randomized algorithm for estimating the volume of a well-rounded convex body given by a membership oracle, improving on the previous best complexity of $O^*(n^4)$ . The new algorithmic ingredient is an accelerated cooling schedule where the rate of cooling increases with the temperature. Previously, the known approach for potentially achieving this asymptotic complexity relied on a positive resolution of the KLS hyperplane conjecture, a central open problem in convex geometry. We also obtain an $O^*(n^3)$ randomized algorithm for integrating a standard Gaussian distribution over an arbitrary convex set containing the unit ball. Both the volume and Gaussian volume algorithms use an improved algorithm for sampling a Gaussian distribution restricted to a convex body. In this latter setting, as we show, the KLS conjecture holds and for a spherical Gaussian distribution with variance $σ^2$ , the sampling complexity is $O^*(\max\{n^3, σ^2n^2\})$ for the first sample and $O^*(\max\{n^2, σ^2n^2\})$ for every subsequent sample.

preprint2013arXiv

A Cubic Algorithm for Computing Gaussian Volume

We present randomized algorithms for sampling the standard Gaussian distribution restricted to a convex set and for estimating the Gaussian measure of a convex set, in the general membership oracle model. The complexity of integration is $O^*(n^3)$ while the complexity of sampling is $O^*(n^3)$ for the first sample and $O^*(n^2)$ for every subsequent sample. These bounds improve on the corresponding state-of-the-art by a factor of $n$ . Our improvement comes from several aspects: better isoperimetry, smoother annealing, avoiding transformation to isotropic position and the use of the "speedy walk" in the analysis.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.