<div dir="ltr"><div><br></div><div>Relevant course at MIT:</div><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Vinod Vaikuntanathan</b> <span dir="ltr">&lt;<a href="mailto:vinod.nathan@gmail.com">vinod.nathan@gmail.com</a>&gt;</span><br>Date: Mon, Sep 4, 2017 at 11:10 PM<br>Subject: Lattice course at MIT<br><div dir="ltr"><div><br></div><div><br></div><div><p class="MsoNormal" style="font-size:12.800000190734863px"><span style="font-size:9.5pt;line-height:13.5533px;font-family:Arial,sans-serif">6.876J ADVANCED TOPICS IN CRYPTOGRAPHY: LATTICES IN COMPUTER SCIENCE (3-0-9, H level)</span><span style="font-size:9.5pt;line-height:13.5533px;font-family:Arial,sans-serif"><br>Instructor: Vinod Vaikuntanathan<br>When: T <span class="m_-8149921327792878038gmail-aBn"><span class="m_-8149921327792878038gmail-aQJ">10-12:30 pm</span></span> (first lecture: <span class="m_-8149921327792878038gmail-aBn"><span class="m_-8149921327792878038gmail-aQJ">Tue 9/12</span></span>)<br>Where: 4-237</span></p><p class="MsoNormal" style="font-size:12.800000190734863px"><span style="font-size:9.5pt;line-height:13.5533px;font-family:Arial,sans-serif"><span style="font-family:arial,sans-serif;font-size:12.800000190734863px">PREREQUISITES: 6.046 and basic linear algebra.</span><br style="font-family:arial,sans-serif;font-size:12.800000190734863px">Class website: <a href="http://people.csail.mit.edu/vinodv/6876-Fall2017/index.html" target="_blank">http://people.csail.m<wbr>it.edu/vinodv/6876-Fall2017/in<wbr>dex.html</a></span></p><p class="MsoNormal" style="font-size:12.800000190734863px"><br></p><p class="MsoNormal" style="font-size:12.800000190734863px"><span style="font-size:9.5pt;line-height:13.5533px;font-family:Arial,sans-serif">Integer Lattices are a formidable tool in mathematics and computer science, with many applications in (algebraic) number theory, coding theory, combinatorial optimization and cryptography. Come to <span class="m_-8149921327792878038gmail-m_-233097266733647661gmail-il">6.876</span> to learn about lattice algorithms, the complexity theory of lattice problems, and their applications in cryptography.</span></p><p class="MsoNormal" style="font-size:12.800000190734863px"><span style="font-size:9.5pt;line-height:13.5533px;font-family:Arial,sans-serif"><br></span></p><p class="MsoNormal" style="font-size:12.800000190734863px"><span style="font-size:9.5pt;line-height:13.5533px;font-family:Arial,sans-serif">A sample of topics we will cover include:</span></p><p class="MsoNormal" style="font-size:12.800000190734863px"><span style="font-size:9.5pt;line-height:13.5533px;font-family:Arial,sans-serif"><br></span></p><p class="MsoNormal" style="font-size:12.800000190734863px"><span style="font-size:9.5pt;line-height:13.5533px;font-family:Arial,sans-serif">1) Lattice Algorithms, starting from Gauss through LLL and AKS</span><span style="font-family:Arial,sans-serif;font-size:9.5pt"> and all the way to brand new developments.</span></p><p class="MsoNormal" style="font-size:12.800000190734863px"><span style="font-size:9.5pt;line-height:13.5533px;font-family:Arial,sans-serif"><br></span></p><p class="MsoNormal" style="font-size:12.800000190734863px"><span style="font-size:9.5pt;line-height:13.5533px;font-family:Arial,sans-serif">2) Complexity of Lattice Problems: Ajtai, Micciancio, Khot and Regev&#39;s NP-hardness (of approximation) results and recent SETH-hardness results (from FOCS&#39;17).<br><br></span></p><p class="MsoNormal" style="font-size:12.800000190734863px"><span style="font-size:9.5pt;line-height:13.5533px;font-family:Arial,sans-serif">3) Cryptography: Starting from Ajtai’s worst-case to average-case reduction, we will see how to build one-way functions, public-key encryption, homomorphic encryption and more.</span></p><p class="MsoNormal" style="font-size:12.800000190734863px"><span style="font-size:9.5pt;line-height:13.5533px;font-family:Arial,sans-serif"><br>Bonus feature this year: We will experiment with regular optional open problem sessions with Professor Erik Demaine. </span></p><p class="MsoNormal" style="font-size:12.800000190734863px"><br></p><p class="MsoNormal" style="font-size:12.800000190734863px">GRADING: The grade will be based on 2-3 problem sets and a final project.</p></div></div>
</div><br></div>