Myfyriwr ymchwil, Yr Ysgol Mathemateg
- M/1.10b, 21-23 Ffordd Senghennydd, Cathays, Caerdydd, CF24 4AG
Mae'r cynnwys hwn ar gael yn Saesneg yn unig.
Lattices and their applications to Cryptography, Number Theory, Linear Algebra
Lattice problems and public-key cryptosystems
It is well known that finding a solution to an integer linear program (ILP) in general is NP-complete. Despite this one can obtain an approximation within polynomial time by solving its related linear program (LP). Because of this it should come as no surprise that a central problem within this research domain is to estimate the distance from an approximate solution (obtained from solving the LP) to some nearby feasible integer solution (that solves the ILP). We will use the term ‘(maximum) vertex distance’ to denote this distance.
My thesis aims to find optimal worst case upper bounds on the (maximum) vertex distance using some fundametal characteristics of the underlying integral constraint matrix.