From: Rosa Teorell (rosat@microsoft.com)
Date: Tue Jan 13 2004 - 12:23:20 PST
You are invited to attend...
************************************************************************
*****************************
WHO: Kevin Woods
AFFILIATION: University of Michigan - Dept of Mathematics
TITLE: Quick Algorithms for Lattice Point Problems
WHEN: Mon 1/19/04
WHERE: 113/1021 Research Lecture Room; Microsoft Research
TIME: 10:30AM-12:00PM
HOST: Jennifer Chayes
************************************************************************
******************************
ABSTRACT:
I will talk about several problems related to lattice points, from an
algorithmic perspective. The Frobenius problem is a good example. Let S
be the set of all numbers representable as a nonnegative integer
combination of given coprime positive integers a_1,...,a_d. What is the
largest integer not in S? How many positive integers are not in S? For
any fixed d, these problems and others admit quick (polynomial time)
algorithms. The main tool I will use is the following theorem: for
fixed d, the generating function of the projection of the set of integer
points in a d-dimensional polytope is computable in polynomial time.
Using this, we can find the generating function of S, as well as of
other interesting sets of lattice points, such as minimal Hilbert bases
and test sets for integer programming.
BIO:
Kevin Woods is a PhD student in Mathematics at the University of
Michigan, and his advisor is Alexander Barvinok. Kevin studies problems
in combinatorics, discrete and computational geometry, and theoretical
computer science.
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Tue Jan 13 2004 - 12:24:00 PST