## DIMACS TR: 97-14

## Computing Integral Points in Convex Semi-algebraic Sets

### Authors: Leonid Khachiyan and Lorant Porkolab

**
ABSTRACT
**

Let $Y$ be a convex set in $R^k$ defined by polynomial inequalities
and equations of degree $d \ge 2$ with integer coefficients of binary
length $l$. We show that if $Y \cap Z^k \ne \emptyset$, then $Y$
contains an integral point of binary length $ld^{O(k^4)}$. For fixed
$k$, our bound implies a polynomial-time algorithm for computing an
integral point $y \in Y$. In particular, we extend Lenstra's theorem
on the polynomial-time solvability of linear integer programming in
fixed dimension to semidefinite integer programming.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-14.ps.gz

DIMACS Home Page