| It is common knowledge that the understanding of the geometry of convex bodies and polyhedra has helped speed up algorithms in discrete optimization. For example, cutting planes and facet-description of polyhedra have been crucial in the success of branch-and-bound algorithms for mixed integer programming. Another example, is how the ellipsoid method can be used to prove polynomiality results in combinatorial optimization. In the past 5 years two beautiful geometric algorithms on polyhedra have been used to prove unexpected new complexity results on the computation of integer programs (both linearly and non-linearly constrained). The first is Barvinok's algorithm for polytopes, the second is the Graver bases algorithm on polyhedral cones. I will describe these two algorithms and explain why we can now prove theorems that were beyond our reach before. I will also describe attempts to use these two algorithms in practical computation, not just in theoretical results. This a survey of results contained in papers joint work with various subsets of the following people: R. Hemmecke, M. Koeppe, S. Onn, U. Rothblum, and R. Weismantel. |