BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Keegan Ryan (UC San Diego)
DTSTART:20230420T210000Z
DTEND:20230420T220000Z
DTSTAMP:20260423T022808Z
UID:UCSD_NTS/89
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/UCSD_NTS/89/
 ">Fast Practical Lattice Reduction through Iterated Compression</a>\nby Ke
 egan Ryan (UC San Diego) as part of UCSD number theory seminar\n\nLecture 
 held in APM 6402 and online.\n\nAbstract\nWe introduce a new lattice basis
  reduction algorithm with approximation guarantees analogous to the LLL al
 gorithm and practical performance that far exceeds the current state of th
 e art. We achieve these results by iteratively applying precision manageme
 nt techniques within a recursive algorithm structure and show the stabilit
 y of this approach. We analyze the asymptotic behavior of our algorithm\, 
 and show that the heuristic running time is $O(n^{\\omega}(C+n)^{1+\\varep
 silon})$ for lattices of dimension $n$\, $\\omega\\in (2\,3]$ bounding the
  cost of size reduction\, matrix multiplication\, and QR factorization\, a
 nd $C$ bounding the log of the condition number of the input basis $B$. Th
 is yields a running time of $O\\left(n^\\omega (p + n)^{1 + \\varepsilon}\
 \right)$ for precision $p = O(\\log \\|B\\|_{max})$ in common applications
 . Our algorithm is fully practical\, and we have published our implementat
 ion. We experimentally validate our heuristic\, give extensive benchmarks 
 against numerous classes of cryptographic lattices\, and show that our alg
 orithm significantly outperforms existing implementations.\n\npre-talk at 
 1:20pm\n
LOCATION:https://researchseminars.org/talk/UCSD_NTS/89/
END:VEVENT
END:VCALENDAR