We show that the volume of a convex body in \(\mathbb {R}^{n}\) specified in the general membership oracle model can be computed to within relative error \(\varepsilon \gt 0\) using \(\widetilde{O}(n^{3.5}\psi ^{2} + n^3/\varepsilon ^{2})\) oracle queries, where \(\psi\) is the KLS constant. With the current bound of \(\psi =\widetilde{O}(1)\) , this gives an \(\widetilde{O}(n^{3.5} + n^3/\varepsilon ^{2})\) algorithm, improving on the Lovász-Vempala \(\widetilde{O}(n^{4}/\varepsilon ^{2})\) algorithm from 2003. The main new ingredient is an \(\widetilde{O}(n^{3}\psi ^{2})\) algorithm for isotropic transformation of a well-rounded convex body; we apply this iteratively to isotropize a general convex body. Following this, we can apply the \(\widetilde{O}(n^{3}/\varepsilon ^{2})\) volume algorithm of Cousins and Vempala for well-rounded convex bodies. We also give an efficient implementation of the new algorithm for convex polytopes defined by m inequalities in \(\mathbb {R}^{n}\) : polytope volume can be estimated in time \(\widetilde{O}(mn^{c+0.5}+mn^{c}/\varepsilon ^{2})\) where c < 3.2 depends on the current matrix multiplication exponent and also improves on the previous best bound.

In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, G, and n agents, A, where each agent i ∈ A has a valuation vij ≥ 0 for each item j ∈ G. In addition, every agent i has a non-negative weight wi such that the weights collectively sum up to 1. The goal is to find an assignment σ : G → A that maximizes . When all the weights equal to , the problem reduces to the classical Nash Social Welfare problem, which has recently received much attention. In this work, we present a -approximation algorithm for the weighted Nash Social Welfare problem, where denotes the KL-divergence between the distribution w and the uniform distribution on [n].

We study a unified approach and algorithm for constructive discrepancy minimization based on a stochastic process. By varying the parameters of the process, one can recover various state-of-the-art results. We demonstrate the flexibility of the method by deriving a discrepancy bound for smoothed instances, which interpolates between known bounds for worst-case and random instances.

Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics [1], convex geometry [2], fair allocations [3], combinatorics [4], spectral graph theory [5], network design, and random processes [6]. In an instance of a determinant maximization problem, we are given a collection of vectors $U=\{v_{1},\cdots,\ v_{n}\}\subset \mathbb{R}^{d}$, and a goal is to pick a subset $S\subseteq U$ of given vectors to maximize the determinant of the matrix $\displaystyle \sum_{i\in S}v_{i}v_{i}^{\text{T}}$. Often, the set S of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint $(|S|\leq k)$ or matroid constraint $(S$ is a basis of a matroid defined on the vectors). In this paper, we give a polynomial-time deterministic algorithm that returns a $r^{O(r)}$-approximation for any matroid of rank $r \leq d$. This improves previous results that give $e^{O(r^{2})}$-approximation algorithms relying on $e^{O(r)}$-approximate estimation algorithms [4], [7] –[9] for any r$\leq$d. All previous results use convex relaxations and their relationship to stable polynomials and strongly $\log$-concave polynomials or non-convex relaxations for the problem [10]. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the $\det(.)$ function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.

The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to 1971. In each step of the Gibbs Sampler, we pick a random coordinate and re-sample that coordinate from the distribution induced by fixing all the other coordinates. While it has become widely used over the past half-century, guarantees of efficient convergence have been elusive. We show that for a convex body K in ℝⁿ with diameter D, the mixing time of the Coordinate Hit-and-Run (CHAR) algorithm on K is polynomial in n and D. We also give a lower bound on the mixing rate of CHAR, showing that it is strictly worse than hit-and-run and the ball walk in the worst case.

We show that the volume of a convex body in Rn in the general membership oracle model can be computed to within relative error ε using O(n3ψ2/ε2) oracle queries, where ψ is the KLS constant. With the current bound of ψ=O(no(1)), this gives an O(n3+o(1)/ε2) algorithm, the first improvement on the Lovász-Vempala O(n4/ε2) algorithm from 2003. The main new ingredient is an O(n3ψ2) algorithm for isotropic transformation, following which we can apply the O(n3/ε2) volume algorithm of Cousins and Vempala for well-rounded convex bodies. A positive resolution of the KLS conjecture would imply an O(n3/є2) volume algorithm. We also give an efficient implementation of the new algorithm for convex polytopes defined by m inequalities in Rn: polytope volume can be estimated in time O(mnc/ε2) where c<3.2 depends on the current matrix multiplication exponent and improves on the previous best bound.

Motivated by the Dikin walk, we develop aspects of the interior-point theory for sampling in high dimension. Specifically, we introduce the notions of strong self-concordance and symmetry for a barrier. These properties imply that the Dikin walk defined using a strongly self-concordant barrier with symmetry parameter ν mixes in Õ(nν) steps from a warm start for a convex body in ℝ n . For many natural barriers, ν is roughly bounded by ν, the standard self-concordance parameter. We also show that these properties hold for the Lee-Sidford barrier. As a consequence, we obtain the first walk that mixes in Õ(n 2) steps for an arbitrary polytope in ℝ n . Strong self-concordance for other barriers leads to an interesting (and unexpected) connection — for the universal and entropic barriers, it is implied by the KLS conjecture.