<div dir="ltr"><div dir="ltr"><div><div><div><div><span class="gmail-m_-7641283104640803278gmail-MathJax" style="display:inline;line-height:normal;float:none;direction:ltr;max-width:none;max-height:none;min-width:0px;min-height:0px;border:0px;padding:0px;margin:0px"><span class="gmail-m_-7641283104640803278gmail-math" style="display:inline;border:0px;padding:0px;margin:0px;vertical-align:0px;line-height:normal"><span class="gmail-m_-7641283104640803278gmail-noError" style="display:inline;border:0px;padding:1px 3px;margin:0px;vertical-align:0px;line-height:normal"><div class="gmail_default" style="font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">When: <span style="font-weight:400">    Thursday, January 24th </span><span class="gmail-m_2297318085548821105gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il" style="font-weight:400">at</span><span style="font-weight:400"> </span><b>11:00 am</b></font></div><div class="gmail_default" style="font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif"><b><br></b></font></div><div class="gmail_default" style="font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">Where:<span style="font-weight:400">    </span><span class="gmail-m_2297318085548821105gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-m_8421504075585210435gmail-m_3262824545120381495gmail-m_-1141671822915777344gmail-m_-7219251726624328345gmail-m_-8588148075564318222gmail-m_-8767966813928691312gmail-m_-1542318334608687154gmail-m_5717104778280916634gmail-m_4845490158781220632gmail-m_5124567205141626540gmail-m_3209361100497750746gmail-m_2953668934074478317gmail-m_-3155518689668024534m_9067904842688472155gmail-m_3071693547520408192gmail-il" style="font-weight:400"><span class="gmail-m_2297318085548821105gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il"><span class="gmail-m_2297318085548821105gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-il">TTIC</span></span></span><span style="font-weight:400">, 6045 S Kenwood Avenue, 5th Floor, Room 526</span></font></div><div class="gmail_default" style="font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif"><span style="font-weight:400"><br></span></font></div><div class="gmail_default"><span style="font-weight:bold;font-family:arial,helvetica,sans-serif;color:rgb(0,0,0)">Who:</span><span style="font-weight:normal;font-family:arial,helvetica,sans-serif;color:rgb(0,0,0)">       </span><font color="#000000" face="arial, helvetica, sans-serif">Talya Eden, Tel Aviv University</font><br></div></span></span></span></div><div><span class="gmail-m_-7641283104640803278gmail-MathJax" style="display:inline;line-height:normal;float:none;direction:ltr;max-width:none;max-height:none;min-width:0px;min-height:0px;border:0px;padding:0px;margin:0px"><span class="gmail-m_-7641283104640803278gmail-math" style="display:inline;border:0px;padding:0px;margin:0px;vertical-align:0px;line-height:normal"><span class="gmail-m_-7641283104640803278gmail-noError" style="display:inline;border:0px;padding:1px 3px;margin:0px;vertical-align:0px;line-height:normal"><b><br></b></span></span></span></div><div><span class="gmail-m_-7641283104640803278gmail-MathJax" id="gmail-m_-7641283104640803278gmail-MathJax-Element-9-Frame" style="display:inline;line-height:normal;float:none;direction:ltr;max-width:none;max-height:none;min-width:0px;min-height:0px;border:0px;padding:0px;margin:0px"><span class="gmail-m_-7641283104640803278gmail-math" id="gmail-m_-7641283104640803278gmail-MathJax-Span-33" style="display:inline;border:0px;padding:0px;margin:0px;vertical-align:0px;line-height:normal"><span class="gmail-m_-7641283104640803278gmail-noError" id="gmail-m_-7641283104640803278gmail-MathJax-Span-34" style="display:inline;border:0px;padding:1px 3px;margin:0px;vertical-align:0px;line-height:normal"><b>Title:       </b>Estimating and Sampling Subgraphs in Sublinaer-Time<br><br><b>Abstract:</b> I will present an algorithm for approximating the number of k-cliques in a graph when given query access to the graph. Let n denote the number of vertices in the graph,  the number of edges, and Ck the number of k-cliques. We design an algorithm that outputs a (1+ε)-approximation (with high probability) for Ck, whose expected query complexity and running time are <font color="#000000" face="Lucida Grande, helvetica, arial, verdana, sans-serif"><span style="font-size:14.4px;white-space:nowrap"><img alt="O\left(\frac{n}{C_k^{1/k}}+\frac{m^{k/2}}{C_k}\right)" title="O\left(\frac{n}{C_k^{1/k}}+\frac{m^{k/2}}{C_k}\right)" class="gmail-m_-7641283104640803278gmail-va_li gmail-CToWUd" src="https://s0.wp.com/latex.php?zoom=3&bg=transparent&fg=000000&s=0&latex=O%5Cleft(%5Cfrac%7Bn%7D%7BC%5Fk%5E%7B1/k%7D%7D%2B%5Cfrac%7Bm%5E%7Bk/2%7D%7D%7BC%5Fk%7D%5Cright)" id="gmail-m_-7641283104640803278gmail-l0.23030672352485104" height="39" width="115" style="display: inline; vertical-align: -10px;"></span></font></span></span></span><span style="color:rgb(0,0,0);font-family:"Lucida Grande",helvetica,arial,verdana,sans-serif;font-size:14.4px">. </span>The main insight is a procedure that samples each k-clique incident to a given set S of vertices with approximately equal probability.  </div></div></div><br class="gmail-Apple-interchange-newline"></div><div><br></div><div>Host: <a href="mailto:Yury@ttic.edu">Yury Makarychev</a></div><div><br></div><div><br></div><div><br></div><br clear="all"><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>