Please provide your feedback about the website at feedback@apc.iisc.ernet.in

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

Department of Computer Science and Automation

Department Seminar

Speaker : Prof.Manindra Agrawal

Professor

Indian Institute of Technology Kanpur

Title : Simultaneous Diophantine Approximation and Short Lattice Vectors

Date : Monday, July 01, 2019

Time : 4:00 PM

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

Abstract

Simultaneous Diophantine approximation (SDA) is the problem of finding an integer multiplier k, within a given upper bound N, of n rational numbers such that all the resulting numbers are delta-close to integers. This problem has a long history with Dirichlet showing that such multiplier exists when N geq (1/delta)^n. Finding such a multiplier, or even deciding if a multiplier exists, is difficult: Lagarias showed that SDA is NP-hard. If one allows certain relaxation in bounds, then the problem becomes easy: Lagarias showed that one can find a k leq 2^n N such that all resulting numbers are 2^ndelta-close to an integer. This was through a reduction of the problem to another one: finding shortest vector in an integer lattice (SVP). SVP is the problem of finding the shortest non-zero vector in the vector space Z[v_1, …, v_n]. SVP is very well studied due to its applications in cryptography. We exhibit a tighter connection of SVP and SDA by showing that SVP reduces to SDA.

Host Faculty : Prof. Chandan Saha

ALL ARE WELCOME