View all Seminars  |  Download ICal for this event

Number of near-shortest vectors in lattices

Series: Department Seminar

Speaker: Dr. Rohit Gurjar Assistant Professor Indian Institute of Technology Bombay P

Date/Time: Dec 27 11:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Faculty Advisor:

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.

Speaker Bio:
Rohit Gurjar is an Assistant Professor at IIT Bombay. His research area is broadly algorithms and complexity. More specifically, he is interested in derandomization, combinatorial optimization, and algebraic algorithms.

Host Faculty: Dr. Siddharth Barman