12
$\begingroup$

What are some concrete and compelling applications for estimating the volume of convex polyhedra of the sort considered in the more recent papers on random walk methods?

These papers on volume estimation mention numerical integration as one motivation. What are examples of integrals that people want to compute in practice which are very hard to compute using previous methods? Or is there some other compelling practical application for computing the volume of a 1000-dimensional polytope?

$\endgroup$
  • $\begingroup$ I wonder if you'll get more responses of the type you're looking for on physics.stackexchange.com... Also, for those of us not familiar with this particular sub-area of theory, could you maybe include some references for "more recent papers on random walk methods"? $\endgroup$ – Joshua Grochow Aug 6 '13 at 1:23
  • $\begingroup$ more thinking on this after answering & poking around. some papers seem to point out, or go in the direction, that calculating the volume of polytope is something like a fundamental problem in complexity theory. this is not surprising given that calculating the determinant is another key problem in complexity theory, and the determinant is the volume of a parallelpiped. so one reasonable answer seems to be that there seem to be deep or natural connections in complexity theory. more evidence of this would be a tie to some specific complexity class.... may dig around more on this.... $\endgroup$ – vzn Aug 6 '13 at 2:36
  • $\begingroup$ see also mathoverflow, algorithm for finding volume of complex polytope. yes this question above asks for applications, not algorithms, but some of the algorithm papers will give motivations/applications. $\endgroup$ – vzn Aug 6 '13 at 2:57
7
+50
$\begingroup$

Estimating the volume of a convex polytope and the closely related task of sampling from it have applications in private data release.

Roughly, the problem you want to solve is: given a collection of numeric valued queries on a database, come up with answers to those questions that are as close as possible to the real answers, while satisfying differential privacy. In some range of parameters, the optimal algorithm for solving this problem has a geometric description, and implementing it involves sampling from a convex polytope. See here: http://arxiv.org/pdf/0907.3754v3.pdf

$\endgroup$
4
$\begingroup$

Polyhedra are widely used in program analysis as a means of representing (an overapproximation of) set of all possible states, where a state records the value of each variable in the program. If there are a set of invariants of the program variables, each of which can be represented as a linear inequality on the variables, then conjoining all of these invariants yields a polyhedron. If $s$ is a possible state of the program, then $s$ will be in the interior of the polyhedron (but not necessarily the reverse).

In computer security, work on quantitative information flow has applied these methods to estimate the amount of confidential information that might be leaked by a particular program. Here we build a polyhedron representing possible states of the program at a particular point in its execution, and then we want to estimate something about the number of possible states (this is related to the amount of information released). Thus, at a certain point in the analysis, they end up trying to count the number of integer points contained inside the polyhedron. This smells related to volume estimation (to me).

Here is an early paper that is representative:

That said, this might not be exactly what you are looking for. It requires methods to count the number of integer points inside the polyhedron, which isn't the same as the volume of the polyhedron. Also, I don't think they need to analyze polyhedra of dimension 1000 or higher (though I'm not sure about that).

$\endgroup$
  • $\begingroup$ Thank you. The problem of finding the number of integer solutions to a set of linear inequalities is #P-complete I think (math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf has some more applications too). Whereas estimating the volume can be done in poly time. You can apparently use the latter to approximate the former but I am really looking for direct concrete applications of volume estimation. $\endgroup$ – user17100 Jul 31 '13 at 7:50
  • $\begingroup$ Computing the volume of a polytope is also #P-hard. By itself, this fact says little about approximations. $\endgroup$ – Sasho Nikolov Jul 31 '13 at 20:26
  • $\begingroup$ @SashoNikolov Volume approximation I believe is impossible deterministically in oracle model while possible in randomized sense. Doesn't it prove $P\neq BPP$ and if not then is there any related fundamental derandomization problem that is open in volume computation? $\endgroup$ – T.... Jul 15 at 11:23
  • 1
    $\begingroup$ @Turbo Obviously it doesn't prove that P is not equal to BPP, because these two classes are not about an oracle model. I believe that deterministically approximating the volume of a polytope represented by inequalities is open. $\endgroup$ – Sasho Nikolov Jul 18 at 15:19
  • $\begingroup$ @SashoNikolov If you might know this seemingly simple problem it would be nice mathoverflow.net/questions/336369/…. $\endgroup$ – T.... Jul 18 at 23:27
4
$\begingroup$

Hari Narayanan recentely posted a paper on the arXiv in which he uses estimating the volume of a convex polytope to prove certain results about the Littlewood-Richardson (LR) coefficients. The LR coefficients are certain integers in representation theory that have applications in geometric complexity theory, particle physics, and many other fields (see the introduction of the above paper for more references). Again, probably not exactly what you wanted, but an interesting connection nonetheless.

$\endgroup$
3
$\begingroup$

see e.g.: N-Dimensional Volume Estimation of Convex Bodies: Algorithms and Applications by Sharma, Prasanna, Aswal for an example/case study in economic forecasting, ie supply chain management.

Our methods can be used to quantify information content and uncertainty, in constraint regions, in a robust optimization framework. We show applications in supply chain management, under conditions of future uncertainty.

basically the idea is that a polytope can model a "future scenario" of parameters of a supply chain management configuration. the uncertainty (or "error") in the model/estimation is taken as proportional to the volume of the polytope(s). see slides 3,4. this then allows:

  • quantitative estimation of uncertainty
  • generation of equivalent information
  • help in what-if analysis
$\endgroup$
  • $\begingroup$ Thank you. These examples are nice but I still find it hard to believe they are what is meant when people say that estimating the volume of a high dimensional convex body is one of the most important applications of the Markov Chain Monte Carlo method. $\endgroup$ – user17100 Aug 5 '13 at 21:33
  • $\begingroup$ agreed the example in the slides is "toy size" as far as # of dimensions but maybe some supply chain management problems have large dimensions in practice. also this line of research seems to suggest to me that it may have some application in some forms of datamining. $\endgroup$ – vzn Aug 6 '13 at 2:40
2
$\begingroup$

heres another angle turned up on some online investigation. the Birkoff polytope $B_n$ has many deep theoretical properties & relates to eg to perfect matchings on graphs, but volume calculations of it are very hard even for low $n$ eg as in this study by Beck and Pixton. a more direct/remarkable TCS connection arises in that a relatively recent paper proposes a measure of graph complexity based on Birkoff polytope calculations.

Birkhoff polytopes, heat kernels and graph complexity by Francisco Escolano, Edwin R. Hancock, Miguel A. Lozano, 2008

$\endgroup$

Your Answer

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