[Colloquium] REMINDER: 1/24 Talks at TTIC: Talya Eden, Tel Aviv University

[Mary Marre via Colloquium]

When:     Thursday, January 24th at *11:00 am*

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       Talya Eden, Tel Aviv University

*Title:       *Estimating and Sampling Subgraphs in Sublinear-Time

*Abstract:* 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 [image: O\left(\frac{n}{C_k^{1/k}}+\frac{m^{k/2}}{C_k}\right)]. The
main insight is a procedure that samples each k-clique incident to a given
set S of vertices with approximately equal probability.


Host: Yury Makarychev <Yury at ttic.edu>



Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*


On Wed, Jan 23, 2019 at 2:24 PM Mary Marre <mmarre at ttic.edu> wrote:

> When:     Thursday, January 24th at *11:00 am*
>
> Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526
>
> Who:       Talya Eden, Tel Aviv University
>
> *Title:       *Estimating and Sampling Subgraphs in Sublinaer-Time
>
> *Abstract:* 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 [image: O\left(\frac{n}{C_k^{1/k}}+\frac{m^{k/2}}{C_k}\right)]. The
> main insight is a procedure that samples each k-clique incident to a given
> set S of vertices with approximately equal probability.
>
>
> Host: Yury Makarychev <Yury at ttic.edu>
>
>
>
>
>
> Mary C. Marre
> Administrative Assistant
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Room 517*
> *Chicago, IL  60637*
> *p:(773) 834-1757*
> *f: (773) 357-6970*
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
>
> On Thu, Jan 17, 2019 at 6:09 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> When:     Thursday, January 24th at *11:00 am*
>>
>> Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526
>>
>> Who:       Talya Eden, Tel Aviv University
>>
>> *Title:       *Estimating and Sampling Subgraphs in Sublinaer-Time
>>
>> *Abstract:* 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 [image: O\left(\frac{n}{C_k^{1/k}}+\frac{m^{k/2}}{C_k}\right)]. The
>> main insight is a procedure that samples each k-clique incident to a given
>> set S of vertices with approximately equal probability.
>>
>>
>> Host: Yury Makarychev <Yury at ttic.edu>
>>
>>
>>
>>
>> Mary C. Marre
>> Administrative Assistant
>> *Toyota Technological Institute*
>> *6045 S. Kenwood Avenue*
>> *Room 517*
>> *Chicago, IL  60637*
>> *p:(773) 834-1757*
>> *f: (773) 357-6970*
>> *mmarre at ttic.edu <mmarre at ttic.edu>*
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190124/6d8b6af7/attachment-0001.html>