BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20191227T120000Z
UID:9164794be0bda4633e7a5e78c9c28982-31
DTSTAMP:19700101T120011Z
DESCRIPTION:Number of near-shortest vectors in lattices
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/31/number-of-near-shortest-vectors-in-lattices/
SUMMARY:For a matrix A, consider the lattice L(A) formed by all integral vectors v in the null-space of A. We ask for which matrices A, the lattice L(A) has only polynomially many near-shortest vectors i.e., vectors whose length is close to the shortest length in L(A). The motivation for this question comes from the fact that we can get a deterministic black-box polynomial identity testing algorithm for any polynomial whose newton polytope has faces described by matrices with the aforementioned property. 
We show that when the matrix A is totally unimodular (all sub-determinants are 0,+1,or -1) then the lattice L(A) has only polynomially many near-shortest vectors. The proof of this statement goes via a remarkable theorem of Seymour on a decomposition for totally unimodular matrices. The statement generalizes two earlier known results -- the number of near-shortest cycles and the number of near-shorest cuts in a graph are poly-bounded. As a special case, we get PIT for any polynomial of the form det(sum x_i A_i) for rank-1 matrices A_i.
DTSTART:20191227T120000Z
END:VEVENT
END:VCALENDAR