<html 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=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Calibri",sans-serif;}
h1
{mso-style-priority:9;
mso-style-link:"Heading 1 Char";
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:24.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
span.Heading1Char
{mso-style-name:"Heading 1 Char";
mso-style-priority:9;
mso-style-link:"Heading 1";
font-family:"Calibri",sans-serif;
font-weight:bold;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
p.code-line, li.code-line, div.code-line
{mso-style-name:code-line;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle20
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style>
</head>
<body lang="EN-US" link="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt">Hi all,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">Following up on Aaron’s magnificent lead, this quarter I am teaching the following topics course. Prerequisites are undergraduate algorithms and a working knowledge of convex optimization and linear algebra.
Feel free to contact me with any questions. <o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">Best wishes for a great quarter,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">Lorenzo<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<h1 style="margin-top:0in"><span style="font-family:"Arial",sans-serif;color:#333333;font-weight:normal">CMSC 35480 Fall 2021: Topics in Optimization: Fast Algorithms via Continuous Optimization and Combinatorial Preconditioning<o:p></o:p></span></h1>
<p class="code-line" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:8.4pt;margin-left:0in;text-align:justify;hyphens: auto;font-variant-ligatures: normal;font-variant-caps: normal;orphans: 2;widows: 2;-webkit-text-stroke-width: 0px;text-decoration-thickness: initial;text-decoration-style: initial;text-decoration-color: initial;word-spacing:0px">
<strong><span style="font-size:10.5pt;font-family:"Arial",sans-serif;color:#333333">Instructor</span></strong><span style="font-size:10.5pt;font-family:"Arial",sans-serif;color:#333333">: Lorenzo Orecchia<br>
<strong><span style="font-family:"Arial",sans-serif">Hours</span></strong>: TR 9.30-10.50am<br>
<strong><span style="font-family:"Arial",sans-serif">Location</span></strong>: JCL 354<o:p></o:p></span></p>
<p class="code-line" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:8.4pt;margin-left:0in;text-align:justify;hyphens: auto;font-variant-ligatures: normal;font-variant-caps: normal;orphans: 2;widows: 2;-webkit-text-stroke-width: 0px;text-decoration-thickness: initial;text-decoration-style: initial;text-decoration-color: initial;word-spacing:0px">
<em><span style="font-size:10.5pt;font-family:"Arial",sans-serif;color:#333333">Note</span></em><span style="font-size:10.5pt;font-family:"Arial",sans-serif;color:#333333">: Meeting times and location may change by consensus of all the course takers and the
instructor.<o:p></o:p></span></p>
<p class="code-line" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:8.4pt;margin-left:0in;text-align:justify;hyphens: auto;font-variant-ligatures: normal;font-variant-caps: normal;orphans: 2;widows: 2;-webkit-text-stroke-width: 0px;text-decoration-thickness: initial;text-decoration-style: initial;text-decoration-color: initial;word-spacing:0px">
<strong><span style="font-size:10.5pt;font-family:"Arial",sans-serif;color:#333333">Topic Area</span></strong><span style="font-size:10.5pt;font-family:"Arial",sans-serif;color:#333333">: In the last decade, techniques from continuous optimization have led
to faster (approximation) algorithms for classical graph problems in combinatorial optimization. Many of these results have relied on the use of a novel framework for algorithm design, based on first-order iterative methods, such as gradient and mirror descent.
Contrary to popular intuition, this is actually a very rich algorithmic class, as all such methods require a choice of underlying, possibly non-Euclidean, geometry (aka preconditioning). Indeed, we will see how to interpret the new algorithms as judicious
combination of the right first-order methods and the right geometry, whose choice often requires an elegant mix of geometric and combinatorial arguments.<o:p></o:p></span></p>
<p class="code-line" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:8.4pt;margin-left:0in;text-align:justify;hyphens: auto;font-variant-ligatures: normal;font-variant-caps: normal;orphans: 2;widows: 2;-webkit-text-stroke-width: 0px;text-decoration-thickness: initial;text-decoration-style: initial;text-decoration-color: initial;word-spacing:0px">
<span style="font-size:10.5pt;font-family:"Arial",sans-serif;color:#333333">In this class, we will explore this novel algorithmic design framework through the lens of minimum-cost maximum-flow tasks, a general family of problems including s-t maximum flow and
s-t shortest paths. We will also take small detours to touch on open problems and current projects in my research group.<o:p></o:p></span></p>
<p class="code-line" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:8.4pt;margin-left:0in;text-align:justify;hyphens: auto;font-variant-ligatures: normal;font-variant-caps: normal;orphans: 2;widows: 2;-webkit-text-stroke-width: 0px;text-decoration-thickness: initial;text-decoration-style: initial;text-decoration-color: initial;word-spacing:0px">
<span style="font-size:10.5pt;font-family:"Arial",sans-serif;color:#333333">For an introduction to the topic, I recommend the 2018 ICM presentation <a href="https://eta.impa.br/dl/028.pdf." title="https://eta.impa.br/dl/028.pdf.">here</a>.<o:p></o:p></span></p>
<p class="code-line" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:8.4pt;margin-left:0in;text-align:justify;hyphens: auto;font-variant-ligatures: normal;font-variant-caps: normal;orphans: 2;widows: 2;-webkit-text-stroke-width: 0px;text-decoration-thickness: initial;text-decoration-style: initial;text-decoration-color: initial;word-spacing:0px">
<strong><span style="font-size:10.5pt;font-family:"Arial",sans-serif;color:#333333">Course Type</span></strong><span style="font-size:10.5pt;font-family:"Arial",sans-serif;color:#333333">: Seminar on current research topics. The instructor and students, working
in groups when possible, will present papers in the topic area. This course does not feature an objectively graded component, so it will not fulfill the Theory requirement for CS PhD students. Ask the instructor about possible projects to complete in conjunction
with the course, if you are interested in having the course count towards requirements.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
</div>
</body>
</html>