<p>Let $A_{n\times n}$ be a positive definite <em>diagonal</em> matrix with positive rational entries, and let $b$ be a positive rational. Let $R(A,b)$ be the ellipsoid
$ \{\mathbf{x}\in \mathbb{R}^n : ||A\mathbf{x}||_2\leq b   \}$.</p>

<blockquote>
  <p>Given the pair $(A,b)$, is it $\mathsf{\#P ~Hard}$ to compute the fraction of the volume of the unit ball $||\mathbf{x}||_2\leq 1$ contained in $R(A,b)$?</p>
</blockquote>

<p>The motivation behind this question is: The answer is "yes" if the 2-norm is replaced with the 1-norm (see <a href="http://epubs.siam.org/doi/abs/10.1137/0217060">Dyer and Frieze</a>). If the answer is "yes" for the 2-norm as well, I would like some tips as to how to do  the reduction, or links to references. This seems to be a reduction from mixed integer quadratic programming (MIQP), but  I'm not sure quite how.</p>

CC BY-SA 3.0
2016-08-31T00:05:48.860Z
I doubt this is hard. I think you should be able to find the two hyperplanes $H_1$ and $H_2$ which contain the two components of the intersection of the sphere with the boundary of $R$. Then the volume of the intersection can be expressed in terms of the volumes of the caps of the ball and $R$ cut off by these hyperplanes. I think there is an analytic formula for the volume of a spherical cap.
Sasho Nikolov
CC BY-SA 3.0
2016-08-31T15:16:24.633Z
@SashoNikolov: I agree with your general idea, but why the boundary of R? Isn't the question about intersecting the interior of the sphere with the interior of the ellipsoid? But
Joshua Grochow
CC BY-SA 3.0
2016-08-31T22:14:47.687Z
What does 'compute' mean here? Specifically since presumably your fraction is going to be irrational more often than not.
Steven Stadnicki
CC BY-SA 3.0
2016-09-01T00:34:03.187Z
@StevenStadnicki that's a good question, and I have to think about it. However, the question is still valid for  inputs that admit a rational output.
Ganesh
CC BY-SA 3.0
2016-09-02T16:12:28.467Z
@JoshuaGrochow actually, I think I was getting the wrong intuition from the three dimensional case. I am not sure what I said makes sense at all anymore. As to "what compute means" I would suggest to look for algorithms that approximate the volume up to $1+\varepsilon$ in time polynomial in the input size and in $\log(1/\varepsilon)$.
Sasho Nikolov
<counting-complexity><high-dimensional-geometry>
Is this volume computation problem #P Hard?
Ganesh
# Is this volume computation problem #P Hard?

(Asked by: username_0 on 2016-08-30)

Let $A\_{n\times n}$ be a positive definite *diagonal* matrix with positive rational entries, and let $b$ be a positive rational. Let $R(A,b)$ be the ellipsoid
$ \{\mathbf{x}\in \mathbb{R}^n : ||A\mathbf{x}||\_2\leq b \}$.

> Given the pair $(A,b)$, is it $\mathsf{\#P ~Hard}$ to compute the fraction of the volume of the unit ball $||\mathbf{x}||\_2\leq 1$ contained in $R(A,b)$?

The motivation behind this question is: The answer is "yes" if the 2-norm is replaced with the 1-norm (see [Dyer and Frieze](http://epubs.siam.org/doi/abs/10.1137/0217060)). If the answer is "yes" for the 2-norm as well, I would like some tips as to how to do the reduction, or links to references. This seems to be a reduction from mixed integer quadratic programming (MIQP), but I'm not sure quite how.

**Tags:** counting-complexity, high-dimensional-geometry

> **Comments:**
> **username_1**: I doubt this is hard. I think you should be able to find the two hyperplanes $H_1$ and $H_2$ which contain the two components of the intersection of the sphere with the boundary of $R$. Then the volume of the intersection can be expressed in terms of the volumes of the caps of the ball and $R$ cut off by these hyperplanes. I think there is an analytic formula for the volume of a spherical cap.  
> **username_2**: @SashoNikolov: I agree with your general idea, but why the boundary of R? Isn't the question about intersecting the interior of the sphere with the interior of the ellipsoid? But  
> **username_3**: What does 'compute' mean here? Specifically since presumably your fraction is going to be irrational more often than not.  
> **username_0**: @StevenStadnicki that's a good question, and I have to think about it. However, the question is still valid for  inputs that admit a rational output.  
> **username_1**: @JoshuaGrochow actually, I think I was getting the wrong intuition from the three dimensional case. I am not sure what I said makes sense at all anymore. As to "what compute means" I would suggest to look for algorithms that approximate the volume up to $1+\varepsilon$ in time polynomial in the input size and in $\log(1/\varepsilon)$.  

---

## 0 answers

