<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=Windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:0 0 0 0 0 0 0 0 0 0;}
@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;}
@font-face
{font-family:"Arial Black";
panose-1:2 11 10 4 2 1 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
p.p1, li.p1, div.p1
{mso-style-name:p1;
margin:0in;
font-size:8.5pt;
font-family:Helvetica;
color:#FF9400;}
span.EmailStyle19
{mso-style-type:personal-reply;
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><!--[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="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="p1"><i><span style="font-size:12.0pt;color:windowtext"> </span></i><o:p></o:p></p>
<p class="p1"><i><span style="font-size:12.0pt;color:#C00000">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="p1"><i><span style="font-size:12.0pt;color:#C00000">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="p1"><i><span style="font-size:12.0pt;color:#C00000">PRESENTS</span></i><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt">
</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica">Vladimir Podolskii</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica;color:black">Visiting Associate Professor,</span></b><o:p></o:p></p>
<p class="MsoNormal" style="margin-right:22.5pt"><b><span style="font-size:12.0pt;font-family:Helvetica;color:black">Courant Institute of Mathematical Sciences, NYU</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:Helvetica"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica"> </span></b><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica"> <img width="208" height="176" style="width:2.1666in;height:1.8333in" id="Picture_x0020_2" src="cid:image001.jpg@01D8FE64.7B126F20" alt="A person in a blue shirt
Description automatically generated with medium confidence"></span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt">Tuesday, November 29, 2022 at 3:30pm</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;background:yellow;mso-highlight:yellow">Kent Chemical Laboratory, Room 107</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal" align="center" style="text-align:center;background:white"><b><span style="font-size:14.0pt;font-family:"Arial",sans-serif;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:8.0pt;mso-line-height-alt:11.75pt"><b><i><span style="font-size:12.0pt">Title:</span></i></b><span style="font-size:12.0pt">
</span><b><span style="font-size:14.0pt;font-family:"Arial",sans-serif;color:black">“</span></b><b><span style="font-size:13.5pt;font-family:"Arial Black",sans-serif;color:black">Constant-Depth Sorting Networks</span></b><b><span style="font-size:14.0pt;font-family:"Arial",sans-serif;color:black">”</span></b><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:8.0pt;line-height:11.75pt"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal" style="text-align:justify"><b><i><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black">Abstract:
</span></i></b><span style="font-size:12.0pt;font-family:"Arial",sans-serif;color:black">We consider sorting networks that are constructed from comparators of arity k>2. That is, in our setting the arity of the comparators — or, in other words, the number of
inputs that can be sorted at the unit cost — is a parameter. We study its relationship with two other parameters — n, the number of inputs, and d, the depth. This model received considerable attention. Partly, its motivation is to better understand the structure
of sorting networks. In particular, sorting networks with large arity are related to recursive constructions of ordinary sorting networks. Additionally, studies of this model have natural correspondence with a recent line of work on constructing circuits for
majority functions from majority gates of lower fan-in.<br>
<br>
We obtain the first lower bounds on the arity of constant-depth sorting networks. More precisely, we consider sorting networks of depth d up to 4, and determine the minimal k for which there is such a network with comparators of arity k. For depths d=1, 2
we observe that k=n. For d=3 we show that k=n/2. For d=4 the minimal arity becomes sublinear: k=\Theta(n^{2/3}). This contrasts with the case of majority circuits, in which k=O(n^{2/3}) is achievable already for depth d=3.</span><o:p></o:p></p>
<p class="MsoNormal" style="text-align:justify"><span style="font-size:12.0pt;font-family:"Arial",sans-serif;color:black"><br>
<br>
The talk is based on joint work with Natalia Dobrokhotova-Maikova and Alexander Kozachinskiy.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="color:black"> </span><o:p></o:p></p>
<p class="MsoNormal" style="line-height:11.75pt"><span style="color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:8.0pt;line-height:11.75pt"><b><i><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Bio:</span></i></b><span style="color:black">
</span><span style="font-size:12.0pt;font-family:"Arial",sans-serif;color:black">Vladimir Podolskii defended his PhD thesis in 2009 in Moscow State University. His research areas are computational complexity, tropical algebra, applications of complexity theory
to databases augmented with logical theories. He is on leave from Steklov Mathematical Institute (Moscow) and a visiting faculty at NYU.</span><o:p></o:p></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica">Host: Alexander Razborov</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica"> </span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt">-- </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black">Jose J Fragoso, Jr</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black">Project Assistant IV</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black">Computer Science Department</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black">John Crerar Library</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black">5730 S. Ellis – Room 200C</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black">Chicago, IL. 60637</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black"><a href="mailto:jfragoso@uchicago.edu" title="mailto:jfragoso@uchicago.edu"><span style="color:#0078D4">jfragoso@uchicago.edu</span></a></span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black">(773) 702-6614</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black">(773) 702-8487 FAX</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black"><img border="0" width="92" height="92" style="width:.9583in;height:.9583in" id="Picture_x0020_1" src="file:////Users/jfragoso/Library/Containers/com.microsoft.Outlook/Data/Library/Caches/Signatures/signature_3234715098" alt="signature_220768276"></span><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
</div>
</body>
</html>