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
