Polynomial time algorithm for approximating the volume of convex bodies

The paper ^[1] is a joint work by Martin Dyer, Alan Frieze and Ravindran Kannan.

The main result of the paper is a randomised algorithm for finding an ${\displaystyle \epsilon }$ approximation to the volume of a convex body ${\displaystyle K}$ in ${\displaystyle n}$-dimensional Euclidean space by assume the existence of a membership oracle. The algorithm takes time bounded by a polynomial in ${\displaystyle n}$, the dimension of ${\displaystyle K}$ and ${\displaystyle 1/\epsilon }$.

The algorithm is a sophisticated usage of the so-called Markov chain Monte Carlo (MCMC) method. The basic scheme of the algorithm is a nearly uniform sampling from within ${\displaystyle K}$ by placing a grid consisting n-dimensional cubes and doing a random walk over these cubes. By using the theory of rapidly mixing Markov chains, they show that it takes a polynomial time for the random walk to settle down to being a nearly uniform distribution.

Algorithmic version for Szemerédi regularity partition

This paper ^[2] is a combined work by Alan Frieze and Ravindran Kannan. They use two lemmas to derive the algorithmic version of the Szemerédi regularity lemma to find an ${\displaystyle \epsilon }$-regular partition.

Lemma 1:
Fix k and ${\displaystyle \gamma }$ and let ${\displaystyle G=(V,E)}$ be a graph with ${\displaystyle n}$ vertices. Let ${\displaystyle P}$ be an equitable partition of ${\displaystyle V}$ in classes ${\displaystyle V_{0},V_{1},\ldots ,V_{k}}$. Assume ${\displaystyle |V_{1}|>4^{2k}}$ and ${\displaystyle 4^{k}>600\gamma ^{2}}$. Given proofs that more than ${\displaystyle \gamma k^{2}}$ pairs ${\displaystyle (V_{r},V_{s})}$ are not ${\displaystyle \gamma }$-regular, it is possible to find in O(n) time an equitable partition ${\displaystyle P'}$ (which is a refinement of ${\displaystyle P}$) into ${\displaystyle 1+k4^{k}}$ classes, with an exceptional class of cardinality at most ${\displaystyle |V_{0}|+n/4^{k}}$ and such that ${\displaystyle \operatorname {ind} (P')\geq \operatorname {ind} (P)+\gamma ^{5}/20}$

Lemma 2:
Let ${\displaystyle W}$ be a ${\displaystyle R\times C}$ matrix with ${\displaystyle |R|=p}$, ${\displaystyle |C|=q}$ and ${\displaystyle \|W\|_{\inf }\leq 1}$ and ${\displaystyle \gamma }$ be a positive real.
(a) If there exist ${\displaystyle S\subseteq R}$, ${\displaystyle T\subseteq C}$ such that ${\displaystyle |S|\geq \gamma p}$, ${\displaystyle |T|\geq \gamma q}$ and ${\displaystyle |W(S,T)|\geq \gamma |S||T|}$ then ${\displaystyle \sigma _{1}(W)\geq \gamma ^{3}{\sqrt {pq}}}$
(b) If ${\displaystyle \sigma _{1}(W)\geq \gamma {\sqrt {pq}}}$, then there exist ${\displaystyle S\subseteq R}$, ${\displaystyle T\subseteq C}$ such that ${\displaystyle |S|\geq \gamma 'p}$, ${\displaystyle |T|\geq \gamma 'q}$ and ${\displaystyle W(S,T)\geq \gamma '|S||T|}$ where ${\displaystyle \gamma '=\gamma ^{3}/108}$. Furthermore, ${\displaystyle S}$, ${\displaystyle T}$ can be constructed in polynomial time.

These two lemmas are combined in the following algorithmic construction of the Szemerédi regularity lemma.

[Step 1] Arbitrarily divide the vertices of ${\displaystyle G}$ into an equitable partition ${\displaystyle P_{1}}$ with classes ${\displaystyle V_{0},V_{1},\ldots ,V_{b}}$ where ${\displaystyle |V_{i}|\lfloor n/b\rfloor }$ and hence ${\displaystyle |V_{0}|<b}$. denote ${\displaystyle k_{1}=b}$.
[Step 2] For every pair ${\displaystyle (V_{r},V_{s})}$ of ${\displaystyle P_{i}}$, compute ${\displaystyle \sigma _{1}(W_{r,s})}$. If the pair ${\displaystyle (V_{r},V_{s})}$ are not ${\displaystyle \epsilon -}$regular then by Lemma 2 we obtain a proof that they are not ${\displaystyle \gamma =\epsilon ^{9}/108-}$regular.
[Step 3] If there are at most ${\displaystyle \epsilon \left({\begin{array}{c}k_{1}\\2\\\end{array}}\right)}$ pairs that produce proofs of non ${\displaystyle \gamma -}$regularity that halt. ${\displaystyle P_{i}}$ is ${\displaystyle \epsilon -}$regular.
[Step 4] Apply Lemma 1 where ${\displaystyle P=P_{i}}$, ${\displaystyle k=k_{i}}$, ${\displaystyle \gamma =\epsilon ^{9}/108}$ and obtain ${\displaystyle P'}$ with ${\displaystyle 1+k_{i}4^{k_{i}}}$ classes
[Step 5] Let ${\displaystyle k_{i}+1=k_{i}4^{k_{i}}}$, ${\displaystyle P_{i}+1=P'}$, ${\displaystyle i=i+1}$ and go to Step 2.