ÿþ<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"> <head> <meta http-equiv=Content-Type content="text/html; charset=unicode"> <meta name=ProgId content=Word.Document> <meta name=Generator content="Microsoft Word 14"> <meta name=Originator content="Microsoft Word 14"> <link rel=File-List href="gems-F12_files/filelist.xml"> <!--[if gte mso 9]><xml> <o:DocumentProperties> <o:Author>Indiana University Northwest</o:Author> <o:Template>Normal</o:Template> <o:LastAuthor>Swastik Kopparty</o:LastAuthor> <o:Revision>12</o:Revision> <o:TotalTime>110</o:TotalTime> <o:Created>2012-09-24T02:55:00Z</o:Created> <o:LastSaved>2012-11-19T13:26:00Z</o:LastSaved> <o:Pages>2</o:Pages> <o:Words>688</o:Words> <o:Characters>3925</o:Characters> <o:Company>IUN</o:Company> <o:Lines>32</o:Lines> <o:Paragraphs>9</o:Paragraphs> <o:CharactersWithSpaces>4604</o:CharactersWithSpaces> <o:Version>14.00</o:Version> </o:DocumentProperties> <o:OfficeDocumentSettings> <o:AllowPNG/> </o:OfficeDocumentSettings> </xml><![endif]--> <link rel=dataStoreItem href="gems-F12_files/item0006.xml" target="gems-F12_files/props007.xml"> <link rel=themeData href="gems-F12_files/themedata.thmx"> <link rel=colorSchemeMapping href="gems-F12_files/colorschememapping.xml"> <!--[if gte mso 9]><xml> <w:WordDocument> <w:SpellingState>Clean</w:SpellingState> <w:GrammarState>Clean</w:GrammarState> <w:TrackMoves>false</w:TrackMoves> <w:TrackFormatting/> <w:PunctuationKerning/> <w:DrawingGridHorizontalSpacing>18 pt</w:DrawingGridHorizontalSpacing> <w:DrawingGridVerticalSpacing>18 pt</w:DrawingGridVerticalSpacing> <w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery> <w:DisplayVerticalDrawingGridEvery>0</w:DisplayVerticalDrawingGridEvery> <w:ValidateAgainstSchemas/> <w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid> <w:IgnoreMixedContent>false</w:IgnoreMixedContent> <w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText> <w:DoNotPromoteQF/> <w:LidThemeOther>EN-US</w:LidThemeOther> <w:LidThemeAsian>X-NONE</w:LidThemeAsian> <w:LidThemeComplexScript>X-NONE</w:LidThemeComplexScript> <w:Compatibility> <w:BreakWrappedTables/> <w:SnapToGridInCell/> <w:WrapTextWithPunct/> <w:UseAsianBreakRules/> <w:DontGrowAutofit/> <w:SplitPgBreakAndParaMark/> <w:EnableOpenTypeKerning/> <w:DontFlipMirrorIndents/> <w:OverrideTableStyleHps/> </w:Compatibility> <w:DoNotOptimizeForBrowser/> <m:mathPr> <m:mathFont m:val="Cambria Math"/> <m:brkBin m:val="before"/> <m:brkBinSub m:val="&#45;-"/> <m:smallFrac m:val="off"/> <m:dispDef m:val="off"/> <m:lMargin m:val="0"/> <m:rMargin m:val="0"/> <m:defJc m:val="centerGroup"/> <m:wrapRight/> <m:intLim m:val="subSup"/> <m:naryLim m:val="subSup"/> </m:mathPr></w:WordDocument> </xml><![endif]--><!--[if gte mso 9]><xml> <w:LatentStyles DefLockedState="false" DefUnhideWhenUsed="false" DefSemiHidden="false" DefQFormat="false" LatentStyleCount="267"> <w:LsdException Locked="false" Priority="1" Name="Default Paragraph Font"/> <w:LsdException Locked="false" Priority="99" Name="No List"/> </w:LatentStyles> </xml><![endif]--> <style> <!-- /* Font Definitions */ @font-face {font-family:Helvetica; panose-1:2 11 6 4 2 2 2 2 2 4; mso-font-charset:0; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:-536859905 -1073711037 9 0 511 0;} @font-face {font-family:Wingdings; panose-1:5 0 0 0 0 0 0 0 0 0; mso-font-charset:2; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:0 268435456 0 0 -2147483648 0;} @font-face {font-family:"Cambria Math"; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:1; mso-generic-font-family:roman; mso-font-format:other; mso-font-pitch:variable; mso-font-signature:0 0 0 0 0 0;} @font-face {font-family:Cambria; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-536870145 1073743103 0 0 415 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; margin-top:0in; margin-right:0in; margin-bottom:10.0pt; margin-left:0in; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Cambria","serif"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Cambria; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} a:link, span.MsoHyperlink {mso-style-unhide:no; color:blue; mso-themecolor:hyperlink; text-decoration:underline; text-underline:single;} a:visited, span.MsoHyperlinkFollowed {mso-style-unhide:no; color:purple; mso-themecolor:followedhyperlink; text-decoration:underline; text-underline:single;} p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph {mso-style-unhide:no; margin-top:0in; margin-right:0in; margin-bottom:10.0pt; margin-left:.5in; mso-add-space:auto; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Cambria","serif"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Cambria; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} p.MsoListParagraphCxSpFirst, li.MsoListParagraphCxSpFirst, div.MsoListParagraphCxSpFirst {mso-style-unhide:no; mso-style-type:export-only; margin-top:0in; margin-right:0in; margin-bottom:0in; margin-left:.5in; margin-bottom:.0001pt; mso-add-space:auto; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Cambria","serif"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Cambria; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} p.MsoListParagraphCxSpMiddle, li.MsoListParagraphCxSpMiddle, div.MsoListParagraphCxSpMiddle {mso-style-unhide:no; mso-style-type:export-only; margin-top:0in; margin-right:0in; margin-bottom:0in; margin-left:.5in; margin-bottom:.0001pt; mso-add-space:auto; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Cambria","serif"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Cambria; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} p.MsoListParagraphCxSpLast, li.MsoListParagraphCxSpLast, div.MsoListParagraphCxSpLast {mso-style-unhide:no; mso-style-type:export-only; margin-top:0in; margin-right:0in; margin-bottom:10.0pt; margin-left:.5in; mso-add-space:auto; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Cambria","serif"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Cambria; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} span.SpellE {mso-style-name:""; mso-spl-e:yes;} .MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; font-size:12.0pt; mso-ansi-font-size:12.0pt; mso-bidi-font-size:12.0pt; font-family:"Cambria","serif"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Cambria; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} @page WordSection1 {size:8.5in 11.0in; margin:1.0in 1.25in 1.0in 1.25in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;} div.WordSection1 {page:WordSection1;} /* List Definitions */ @list l0 {mso-list-id:121387156; mso-list-type:hybrid; mso-list-template-ids:-1387477544 67698689 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;} @list l0:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l0:level2 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New";} @list l0:level3 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l0:level4 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l0:level5 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New";} @list l0:level6 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l0:level7 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l0:level8 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New";} @list l0:level9 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l1 {mso-list-id:832456591; mso-list-type:hybrid; mso-list-template-ids:-587984640 67698689 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;} @list l1:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l1:level2 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New";} @list l1:level3 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l1:level4 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l1:level5 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New";} @list l1:level6 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l1:level7 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l1:level8 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New";} @list l1:level9 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l2 {mso-list-id:1367829907; mso-list-type:hybrid; mso-list-template-ids:-270997132 67698693 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;} @list l2:level1 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l2:level2 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New";} @list l2:level3 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l2:level4 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l2:level5 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New";} @list l2:level6 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l2:level7 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l2:level8 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New";} @list l2:level9 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l3 {mso-list-id:1391878623; mso-list-type:hybrid; mso-list-template-ids:-232762668 67698689 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;} @list l3:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l3:level2 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New";} @list l3:level3 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l3:level4 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l3:level5 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New";} @list l3:level6 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l3:level7 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l3:level8 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New";} @list l3:level9 {mso-level-number-format:bullet; mso-level-text:§ð; mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} ol {margin-bottom:0in;} ul {margin-bottom:0in;} --> </style> <!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:""; mso-padding-alt:0in 5.4pt 0in 5.4pt; mso-para-margin:0in; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Cambria","serif"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin;} </style> <![endif]--><!--[if gte mso 9]><xml> <o:shapedefaults v:ext="edit" spidmax="1026"/> </xml><![endif]--><!--[if gte mso 9]><xml> <o:shapelayout v:ext="edit"> <o:idmap v:ext="edit" data="1"/> </o:shapelayout></xml><![endif]--> </head> <body lang=EN-US link=blue vlink=purple style='tab-interval:.5in'> <div class=WordSection1> <p class=MsoNormal><b><span style='font-size:18.0pt'>Algebraic Gems of Theoretical Computer Science</span></b><span style='font-size:18.0pt'><o:p></o:p></span></p> <p class=MsoNormal><b>Seminar in Computer Science<span style='mso-spacerun:yes'>    </span>16:198:672<o:p></o:p></b></p> <p class=MsoNormal align=center style='text-align:center'><b><o:p>&nbsp;</o:p></b></p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'>Instructor:</b> <span class=SpellE>Shubhangi</span> <span class=SpellE>Saraf</span> </p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'>Email:</b><span style='mso-spacerun:yes'>   </span>shubhangi.saraf@gmail.com</p> <p class=MsoNormal><b>Timing: </b>Mon, Wed 3:20pm  4:40 pm<span style='font-size:11.0pt;font-family:"Helvetica","sans-serif";color:#111111'><o:p></o:p></span></p> <p class=MsoNormal><b>Location:<span style='mso-spacerun:yes'>  </span></b><span style='mso-bidi-font-weight:bold'>HILL 005<o:p></o:p></span></p> <p class=MsoNormal><b>Office hours: </b>Wed 1pm  2 pm (Hill 426)<span style='font-size:11.0pt;font-family:"Helvetica","sans-serif";color:#111111'><o:p></o:p></span></p> <p class=MsoNormal><o:p>&nbsp;</o:p></p> <p class=MsoNormal>In the last few decades, algebraic methods have proven to be extremely powerful in several areas of computer science. Many of the recent and important advances in the field have relied on very simple properties of polynomials. In this course we will see many interesting and often surprising applications of linear algebra and polynomials to complexity theory, cryptography, combinatorics, and algorithm design. We will develop all the algebraic tools that we need along the way.</p> <p class=MsoNormal>No background in algebra will be necessary. However it might be helpful to have some familiarity with discrete math/algorithms and linear algebra. The only real prerequisite is some mathematical maturity. Students with an interest in discrete mathematics and/or theoretical computer science are welcome.</p> <p class=MsoNormal><o:p>&nbsp;</o:p></p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'><span style='font-size:14.0pt'><a href="hw1.pdf">Homework 1</a> <o:p></o:p></span></b></p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'><span style='font-size:14.0pt'><a href="hw2.pdf">Homework 2</a> <o:p></o:p></span></b></p> <p class=MsoNormal><o:p>&nbsp;</o:p></p> <p class=MsoNormal><o:p>&nbsp;</o:p></p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'><span style='font-size:14.0pt'>Schedule:<o:p></o:p></span></b></p> <p class=MsoListParagraphCxSpFirst style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 1 (Wed 09/05): </b>Administrative details, course overview, linear algebra review</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 2 (Mon 09/10): </b>Odd-town, Even-town, fast matrix multiplication (<span class=SpellE>Strassen</span>), integer multiplication, </p> <p class=MsoListParagraphCxSpMiddle><b style='mso-bidi-font-weight:normal'><span style='mso-tab-count:3'>                                    </span><span style='mso-spacerun:yes'>          </span></b>Verifying matrix multiplication, finding triangles in graphs </p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 3 (Wed 09/12): </b>Fast polynomial multiplication using FFT </p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 4 (Mon 09/17): </b>Fast polynomial division, Graph spectrum</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 5 (Wed 09/19): </b>Eigenvalues and expanders, edge expansion, random walks on expanders</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 6 (Mon 09/24): </b>More expanders - expander mixing, randomness reduction</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 7 (Wed 09/26):</b> Introduction to Error Correcting Codes</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 8 (Mon 09/01):</b> Basic bounds for codes</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 9 (Wed 09/03): </b>Codes based on polynomials, Reed Solomon Codes, Reed Muller Codes,<span style='mso-spacerun:yes'>  </span><span style='mso-tab-count:2'>                        </span><span style='mso-spacerun:yes'>                             </span><span style='mso-tab-count:4'>                                           </span><span style='mso-spacerun:yes'>          </span>Schwartz-<span class=SpellE>Zippel</span> Lemma<b style='mso-bidi-font-weight:normal'><o:p></o:p></b></p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 10 (Mon 10/08):</b> <span class=SpellE>Berlekamp</span>-Welch Algorithm for decoding RS codes</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 11 (Wed 10/10):</b> Bounds for <span class=SpellE>Kakeya</span> Sets, Local algorithms for Codes,<span style='mso-spacerun:yes'>                                            </span><span style='mso-tab-count:8'>                                                                                                </span><span style='mso-spacerun:yes'> </span>Permanent is random self reducible </p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 12 (Mon 10/15):</b> Cancelled</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 13 (Wed 10/17):</b> Guest lecture by Raghu: Linear algebraic techniques for discrepancy</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 14 (Mon 10/22):</b> Method of multiplicities</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 15 (Wed 10/24):</b> <span class=SpellE>Razborov</span> <span class=SpellE>Smolensky</span>: Lower bounds for AC0 circuits</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 16 (Mon 10/29):</b> Cancelled due to Sandy</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 17 (Wed 10/31):</b> Cancelled due to Sandy</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 18 (Mon 11/05):</b> Interactive Proofs: </p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 19 (Wed 11/07): </b>#SAT in IP</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 20 (Mon 11/12): CANCELLED </b>(Makeup class on Nov 30, 1pm- 4pm, in Core A 301)</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 21 (Wed 11/14): CANCELLED </b>(Makeup class on Nov 30, 1pm- 4pm, in Core A 301)</p> <p class=MsoListParagraphCxSpMiddle><o:p>&nbsp;</o:p></p> <p class=MsoListParagraphCxSpLast style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'>Lecture 22 (Mon 11/19):</b> Polynomial identity testing, graph <span class=SpellE>matchings</span><o:p></o:p></p> <p class=MsoNormal style='margin-left:.25in'><o:p>&nbsp;</o:p></p> <p class=MsoNormal><o:p>&nbsp;</o:p></p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'><span style='font-size:14.0pt'>Useful references/related material:<o:p></o:p></span></b></p> <p class=MsoListParagraphCxSpFirst style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]>Linear algebra method: <a href="http://gowers.wordpress.com/2008/07/31/dimension-arguments-in-combinatorics/">Blog post</a> by <span class=SpellE>Gowers</span></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><a href="http://people.csail.mit.edu/madhu/ST12/">Course notes</a> by <span class=SpellE>Madhu</span> Sudan (Algebra and computation)</p> <p class=MsoListParagraphCxSpLast style='text-indent:-.25in;mso-list:l2 level1 lfo2'><![if !supportLists]><span style='font-family:Wingdings;mso-fareast-font-family:Wingdings;mso-bidi-font-family: Wingdings'><span style='mso-list:Ignore'>§<span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]>Beautiful <a href="expanders.pdf">survey on expanders</a> by <span class=SpellE>Hoory</span>, <span class=SpellE>Linial</span> and <span class=SpellE>Wigderson</span></p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'><o:p>&nbsp;</o:p></b></p> <p class=MsoNormal><o:p>&nbsp;</o:p></p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'>A tentative (and partial) list of topics that we will cover:<o:p></o:p></b></p> <p class=MsoListParagraphCxSpFirst style='text-indent:-.25in;mso-list:l3 level1 lfo4'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]>Applications of linear algebra</p> <p class=MsoListParagraphCxSpMiddle style='margin-left:1.0in;mso-add-space: auto;text-indent:-.25in;mso-list:l3 level2 lfo4'><![if !supportLists]><span style='font-family:"Courier New";mso-fareast-font-family:"Courier New"'><span style='mso-list:Ignore'>o<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp; </span></span></span><![endif]>(Eigenvalues and expansion in graphs, Applications of dimension and rank arguments, random projections)</p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l3 level1 lfo4'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]>&nbsp; Polynomials in cryptography and complexity theory</p> <p class=MsoListParagraphCxSpMiddle style='margin-left:1.0in;mso-add-space: auto;text-indent:-.25in;mso-list:l3 level2 lfo4'><![if !supportLists]><span style='font-family:"Courier New";mso-fareast-font-family:"Courier New"'><span style='mso-list:Ignore'>o<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp; </span></span></span><![endif]>(Secret sharing, Secure multiparty computation, IP = PSPACE, PCP theorem)</p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l3 level1 lfo4'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]>Design and analysis of error correcting codes (encoding and decoding algorithms) and other combinatorial structures, construction of pseudorandom objects such as randomness extractors and pseudorandom generators</p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l3 level1 lfo4'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]>Applications of Fourier analysis</p> <p class=MsoListParagraphCxSpLast style='text-indent:-.25in;mso-list:l3 level1 lfo4'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]>Introduction to arithmetic circuits/arithmetic computation and polynomial identity testing</p> <p class=MsoNormal><o:p>&nbsp;</o:p></p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'>Grading:</b><span style='mso-spacerun:yes'>    </span>70% homework and 30% presentation</p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'>Homework:</b><span style='mso-spacerun:yes'>  </span>There will be 2 or 3 problem sets over the semester</p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'>Presentations:</b><span style='mso-spacerun:yes'>  </span>Students will be required to give short presentations on research papers on topics related to the material we will cover in class. Suggested topics for the presentations will be provided later on.</p> <p class=MsoNormal><o:p>&nbsp;</o:p></p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'>Some References:<o:p></o:p></b></p> <p class=MsoListParagraphCxSpFirst style='text-indent:-.25in;mso-list:l0 level1 lfo6'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]>Linear Algebra Methods in Computer Science (By Laszlo <span class=SpellE>Babai</span><span style='mso-spacerun:yes'>  </span>and Peter <span class=SpellE>Frankl</span>)</p> <p class=MsoListParagraphCxSpLast style='text-indent:-.25in;mso-list:l0 level1 lfo6'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]>Thirty-three miniatures: Mathematical and Algorithmic Applications of Linear Algebra<span style='mso-spacerun:yes'>  </span>(By Jiri <span class=SpellE>Matousek</span>)</p> <p class=MsoNormal><o:p>&nbsp;</o:p></p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'>Related Courses:<o:p></o:p></b></p> <p class=MsoListParagraphCxSpFirst style='text-indent:-.25in;mso-list:l1 level1 lfo8'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]>Algebra and Computation (by <span class=SpellE>Madhu</span> Sudan)<b style='mso-bidi-font-weight:normal'><o:p></o:p></b></p> <p class=MsoListParagraphCxSpMiddle style='text-indent:-.25in;mso-list:l1 level1 lfo8'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]>Polynomials and Computation (by David Zuckerman)<b style='mso-bidi-font-weight:normal'><o:p></o:p></b></p> <p class=MsoListParagraphCxSpLast style='text-indent:-.25in;mso-list:l1 level1 lfo8'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]>Algebraic Methods in Combinatorics and Computer Science (by Amir <span class=SpellE>Shpilka</span>)<b style='mso-bidi-font-weight: normal'><o:p></o:p></b></p> <p class=MsoNormal><o:p>&nbsp;</o:p></p> </div> </body> </html>