# OLD PAPERS

Here you can find an old collection of some papers in older versions.
I do not maintain the latest there anymore.

## Some of my old papers in ALGEBRAIC OPTIMIZATION/COMPUTATION

The paper surveys several techniques
to exactly count or estimate the number of lattice points inside a bounded
polyhedral region in space.

In the paper Computation in Multicriteria Matroid Optimization
Using recent work on algorithmic theory for nonlinear and multicriteria
matroid optimization, we have developed algorithms and heuristics aimed at
practical solution of large instances of some of these difficult problems. Our
methods primarily use the local adjacency structure inherent in matroid
polytopes to pivot to feasible solutions which may or may not be optimal. We
also present a modified breadth-first-search heuristic that uses adjacency to
enumerate a subset of feasible solutions. We present other heuristics, and
provide computational evidence supporting our techniques. We
implemented all of our algorithms in the software package MOCHA.

In the paper How to integration a
polynomial over a simplex We did a thorough investigation of how
to do exact integration of a polynomial over a simplex and more
generally, convex polyhedral regions. Will appear in Mathematics of
Computation.

The paper Computing Infeasibility
Certificates for combinatorial problems through Hilbert's
Nullstellensatz continues our development of the Nullstellensatz
Linear Algebra algorithm (NulLA) from both a computational and a
theoretical perspective. From the computational perspective, we
compare computations over the rationals to computations over finite
fields; we discuss mathematical ideas for optimizing NulLA ranging
from the algebraic to the probabilistic (e.g., using symmetries), and
we report on experiments proving the non-$3$-colorability of graphs
with almost two thousand vertices and tens of thousands of edges.
A shorter version appeared in the proceedings
of ISSAC 2008. It does not contain all the results of the full version.

In a paper recently submitted to IPCO 2010
, we have improved NulLA (both in theory and practice), by
creating a variation of the Border bases algorithm, called FPNulLA. We
discuss the performance of NulLA and FPNulLA (much better than
NulLA). We use these two algorithms, as well as Gr\"obner bases and
the Theta bodies of Gouveia, Parrilo and Thomas, for the recognition
of combinatorial properties such as $k$-colorability, unique
Hamiltonicity, and automorphism rigidity of graphs. We report on
computational complexity bounds, structural results.

The paper Computation with
Polynomial Equations and Inequalities arising in Combinatorial
Optimization is a survey of the use of algebraic techniques
in combinatorial optimization. The techniques we
discuss here use the algebra of multivariate polynomials with coefficients
over a field to create large-scale linear algebra or semidefinite
programming relaxations of many kinds of feasibility or optimization
questions.

The paper Pareto Optima of Multicriteria
Integer Linear Programs proves a generalization of Lenstra's
theorem for integer programming in fixed dimension. In this case, a
multiobjective integer linear optimization problem with fixed number
of variables and a fixed number of objective functions can be solved
in polynomial time. This paper appeared in * INFORMS journal of
Computing.*

The paper Integer polynomial optimization in
fixed dimension settles the computational complexity of this kind
of integer programs and then gives an FPTAS for the problem of finding
approximations to the maximization of a polynomial over the lattice
points of a polyhedron. A ground breaking result in non-linear integer
programming. It appeared in * Mathematics of Operations Research*

Also accepted in * Mathematical Programming * is our
follow up paper on the the
mixed-integer case for the same problem above.

Test sets are important tools in Algebraic Optimization. Recently
we wrote two papers on a nice situation when the computation of Graver
bases can be efficiently done and optimization can also be carried on
efficiently: First, to appear in the journal * Discrete Optimization *
is a prove that n-fold integer linear programs
can be solved efficiently. There is a follow-up paper to appear in
the * Journal of Pure and Applied Algebra * where we deal with
convex objective maximization problems n-fold convex
maximization

The paper All Linear and Integer
Programs are Slim 3-way Transportation Programs (joint with
S. Onn) presents a polynomial time algorithm that encodes ANY convex
rationalpolyhedron as a 3-way transportation polytope. This means
that3-way transportation polytopes are as nasty as any general
polytope.This has consequences in Discrete Optimization and
Statistics. The software implementing this
algorithm is available here too. This paper appeared in SIAM journal
of Optimization

## OLD papers in COMBINATORICS

The paper Ehrhart polynomials of matroids
and polymatroids (joint with D. Haws and M. Koeppe) shows a curious
family of polytopes whose dimension grows yet we can efficiently compute
their Ehrhart polynomials (we dont know many of them).

The paper On the computation of
Clebsch-Gordan coefficients and the dilation effect (joint with
T.B. McAllister) we investigate the problem of computing tensor
product multiplicities for complex semisimple Lie algebras. Remarkable
new conjectures generalizing the saturation theorem are proposed (the
dilation effect). Download software from Tyrrell's web page.

The paper The many aspects of counting
lattice points in polytopes is a survey of the applications, theory
and algorithms for the problem in the title.

The paper Effective Lattice Point Counting in
Rational Convex Polytopes (joint with R. Hemmecke, J. Tauzer and R. Yoshida) presents the software ** LATTE **
the first full implementation of Barvinok's algorithm. The paper discusses our tricks to implement it, a ``polar'' variation that runs faster in practice, and presents LOTS of concrete calculations and applications (e.g explicit Ehrhart quasipolynomials). For more information on LattE,
please see LattE's home page

Here is an example, in MAPLE, of our formula for the
volume of the Birkhoff polytope $B_3$.

The paper Algebraic Unimodular Counting
(joint with B. Sturmfels) This was the great-grand father of the LATTE
project. The paper presents several computational results regarding
counting unimodular vector partition functions, in particular the
problem of counting Contingency tables and Kostant's partition
function of the root system A_n.
You can also play online with
Kostant's partition function and download software for counting
contingency table here