<div dir="ltr"><div dir="ltr"><div><div class="gmail_default" style="font-size:small"><font style="font-family:arial,sans-serif;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="font-family:arial,sans-serif;color:rgb(80,0,80);vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(0,0,0)">     Wednes</font><span class="gmail_default" style="color:rgb(0,0,0)">day, December 4<span class="gmail_default">, </span>2024</span><font style="color:rgb(0,0,0)"> at</font><b style="color:rgb(0,0,0)"> <span style="background-color:rgb(255,255,0)"><u>11:00</u></span></b><span style="background-color:rgb(255,255,0)"><b><u><font color="#000000"> am</font></u></b><b><u><font color="#000000"> CT</font></u><font color="#000000">   </font></b></span></font></font></div><div class="gmail_default"><div class="gmail_default"><div class="gmail_default"><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b><font color="#500050" face="arial, sans-serif"><br></font></b></p><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><b><font color="#500050">Where:       </font></b><font color="#000000">Talk will be given </font><font color="#000000" style="font-weight:bold"><u>live, in-person</u></font><font style="font-weight:bold"> </font>at<br></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050">               </font><font color="#000000">    TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000">                   5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px">Virtually:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px">   <i>via panopto: </i><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=5e0c8d50-c0f3-4d13-80f5-b23a014e312e" target="_blank"><b>livestream</b></a></span></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b style="color:rgb(60,64,67);letter-spacing:0.2px"><font size="1"><font face="georgia, serif">                     </font></font></b><font face="arial, sans-serif"><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><span style="color:rgb(60,64,67);letter-spacing:0.2px"><b><font face="arial, sans-serif">                     </font></b></span></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(80,0,80);vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b> <font color="#500050">    </font><font color="#000000"><font color="#500050">    </font></font></font></font></font>Meghal Gupta, UC Berkeley</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div style="border-top:none;border-right:none;border-left:none;border-bottom:2.25pt solid rgb(11,118,159);padding:0in 0in 1pt"></div><div><br></div></div></div><div class="gmail_default"><div dir="ltr"><div><font face="arial, sans-serif"><b>Title</b>:          Optimal Quantile Estimation: Beyond the Comparison Mode</font></div><div><font face="arial, sans-serif"><b><br>Abstract: </b>Estimating the median of a stream is one of the most basic problems in data sketching. Precisely, given a stream x<span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"><span style="vertical-align:sub">1</span></span><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline">, x</span><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"><span style="vertical-align:sub">2</span></span><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline">, x</span><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"><span style="vertical-align:sub">3</span></span><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline">, …, x</span><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"><span style="vertical-align:sub">n</span></span><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"> of elements from some universe of size U and an accuracy ε, the goal is to give a space/time-efficient algorithm that outputs an element with rank between (1/2-ε)n and (1/2+ε)n. Estimating arbitrary quantiles has the same space/time complexity as estimating the median.<br><br>The simplest approach to quantile (or median) estimation stores every element individually, requiring nlogU memory. However, numerous algorithms have been developed that achieve significantly better bounds. Despite these results, the optimal algorithm was not known prior to this work. In this talk, we will describe an optimal deterministic quantile sketch that uses O(ε<span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"><span style="vertical-align:super">-1</span></span><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline">·(logn+logU)) bits of memory. This improves upon the previous best deterministic algorithm (Greenwald and Khanna 2003) and even upon the best randomized algorithm (Karnin, Lang, and Libery 2016).</span></span></font></div><div><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"><font face="arial, sans-serif"><br>This is joint work with Mihir Singhal and Hongxun Wu.</font></span></span></div><div><font face="arial, sans-serif"><br></font></div><div><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"><font face="arial, sans-serif"><b>Bio: </b>Hi! My name is <span>Meghal</span>, and I'm a 3rd year graduate student at UC Berkeley. My interests lie primarily in streaming algorithms and error-correcting codes, but I like working on most combinatorial areas of TCS. I'm fortunate to be advised by Professor Venkatesan Guruswami.<span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"></span></font></span></div><div><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"><font face="arial, sans-serif"><br></font></span></div></div><div><div id="m_-8212387801566745501m_7411707280472495348m_3782265693376625181m_-4426915116206566893m_-8269051215838676082m_-4857504361292392405m_-7894017567204943m_-4885984857739340928m_-7774452752044639306m_4484082192933670602m_-1727381471164456222m_-748841883188655251m_611962526655464537m_-2291386001826280818m_8446205837173851621m_8555462040290332708m_6451956535360448322m_-6976229087647104413m_7917979885129397482m_-5423657134431402203m_-1337599008586739890m_8237382617653311322m_-1231130334284673048m_-1282025577005441955m_-1973358356214118865m_-5815637555669013367m_1779572315514282115m_-4485402625451270420m_1520697528942856564m_5948359943660736735m_-4789039193346764527m_3599676094611771654m_8264976978369198918m_7474850050874458051m_5107577024390010371m_253820422674989860m_3983419646637522536m_-7220900540036838011gmail-:qg" role="button" aria-label="Show trimmed content" aria-expanded="false"><font face="arial, sans-serif"><b>Host: </b><a href="mailto:avrim@ttic.edu" target="_blank"><b>Avrim Blum</b></a> and <a href="mailto:siddharth@ttic.edu" target="_blank"><b>Siddharth Bhandari</b></a></font></div></div></div></div><div class="gmail_default"><font face="arial, sans-serif"><br></font></div><div class="gmail_default"><div><br></div><div><br></div><div><br></div><div><br></div></div></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>
</div>