BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
X-WR-CALNAME:CS Seminar Series: Noah Stephens-Davidowitz
X-WR-TIMEZONE:Eastern Time (US & Canada)
BEGIN:VEVENT
DTSTAMP:20260809T015725Z
UID:tag:localist.com\,2008:EventInstance_51001326925200
DTSTART:20251020T160000Z
DTEND:20251020T170000Z
DESCRIPTION:Lattices in Theoretical Computer Science and Cryptography - Som
 e Snippets from a >40-Year History\n\n \n\nAbstract:\n\nWe will try to tel
 l some of the story of lattices in theoretical computer science and crypto
 graphy.\n\n \n\nWe start with (1) the celebrated LLL algorithm from 1982
 —an incredibly useful algorithm that solves a seemingly not-so-useful pr
 oblem—and the central role that lattices played in breaking many early c
 ryptographic schemes.\n\n \n\nWe will then move to (2) Ajtai’s amazing w
 orst-case to average-case reduction from 1996\, showing how to build secur
 e secret-key cryptography under the assumption that a certain *worst-case*
  *approximate* lattice problem is hard. We will then see how around the sa
 me time\, (3) Ajtai proved that the exact version of this problem was NP-h
 ard (resolving a decades-old open question)\, which was followed by a seri
 es of NP-hardness of approximation results with progressively larger appro
 ximation factors. Together\, these results led to speculation and hope tha
 t lattice techniques might lead us to one of the holy grails of cryptograp
 hy: proof that cryptography exists under the minimal assumption that BPP =
 /= NP---all one had to do was show NP-hardness for an approximation factor
  large enough to be compatible with Ajtai's worst-case to average-case red
 uction!\n\n \n\nThis hope was basically quashed by (4) Goldreich and Goldw
 asser's simple and elegant 1998 proof system for approximate lattice probl
 ems\, suggesting that NP-hardness was unlikely.  Though this result largel
 y ruled out a very exciting line of research\, it also introduced powerful
  and beautiful tools that have found innumerable applications in lattice c
 ryptography and beyond.\n\n \n\nFinally\, we will discuss (5) Regev's wors
 t-case to average-case reduction from 2005\, showing how to build secure *
 public-key* cryptography\, again under the assumption that a certain worst
 -case approximate lattice problem is hard. This result led to a revolution
  in cryptography\, with applications ranging from fully homomorphic encryp
 tion to the post-quantum cryptographic schemes that will be running the in
 ternet shortly.\n\n \n\nAnd\, time permitting\, I’ll say a bit about my 
 own work in this field.\n\n \n\nBio:\n\nNoah is an assistant professor in 
 Cornell's computer science department. His research to date has focused pr
 imarily on the study of lattices. He is also interested more broadly in th
 eoretical computer science\, cryptography\, and geometry. He received his 
 PhD from NYU\, advised by Professors Oded Regev and Yevgeniy Dodis. Before
  coming to Cornell\, he was a fellow at the Simons Institute in Berkeley\,
  a postdoctoral researcher at MIT's computer science department\, and a po
 stdoc at Princeton’s computer science department.
GEO:43.126069;-77.629191
LOCATION:Wegmans Hall\, 1400
SUMMARY:CS Seminar Series: Noah Stephens-Davidowitz
URL;VALUE=URI:https://events.rochester.edu/event/cs-seminar-series-noah-ste
 phens-davidowitz
CATEGORIES:Lectures & Talks
END:VEVENT
END:VCALENDAR