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). 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Aug 31 '16 at 0:05
  • $\begingroup$ @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 $\endgroup$ – Joshua Grochow Aug 31 '16 at 15:16
  • $\begingroup$ What does 'compute' mean here? Specifically since presumably your fraction is going to be irrational more often than not. $\endgroup$ – Steven Stadnicki Aug 31 '16 at 22:14
  • $\begingroup$ @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. $\endgroup$ – Ganesh Sep 1 '16 at 0:34
  • $\begingroup$ @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)$. $\endgroup$ – Sasho Nikolov Sep 2 '16 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.