Computational Polyhedral Geometry: Applications in Algebra, Combinatorics, and Optimization

点击翻译按钮获取中文摘要

The investigator uses methods from commutative algebra,convexity, and analysis to design computer algorithms that allowthe practical fast detection or counting of lattice points insiderational convex polytopes. The main idea is to represent thelattice points using rational functions. This can be done in atleast three different complementary ways. He implements themethods in the computer software LattE. The investigator usesthis software to help investigate theoretical questions incombinatorics (properties of Ehrhart functions), algebra(representation theory and partitions), and optimization (newinteger programming algorithms). The investigator carries out geometric, analytic, andcomputational studies of problems in the convexity andcombinatorics of polyhedra, including development of algorithmsand software. Informally speaking, the project can be thought ofas an attempt to understand how to count the possiblenon-negative integer solutions of a system of linear equations.With two unknowns, this amounts to counting the number ofregularly distributed points -- lattice points -- in a polygon.With more unknowns, the solutions correspond geometrically to thehigher-dimensional analogs to cubes and polygons. Examples ofregularly distributed points are arrangements of atoms orcrystals. Many of the theoretical questions under study aremotivated by problems in data security and computation (in thecontext of RSA encryption, which is used in internettransactions), operations research (via certain techniques forsolving integer programs when levels of uncertainty areexpected), statistics (contingency tables, data analysis), andproblems in abstract algebra (number theory, representationtheory). The training of students is a very important componentof the project.