[Colloquium] REMINDER: 1/10 Talks at TTIC at 10:30am: Thatchaphol Saranurak, KTH Royal Institute of Technology

[Mary Marre via Colloquium]

When:     Wednesday, January 10th at *10:30 am *

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

Who:       Thatchaphol Saranurak, KTH Royal Institute of Technology


Title:        Dynamic Spanning Forest: Techniques and Connections to Other
Fields

Abstract: I will first give an overview of dynamic algorithms and their
connections to other fields. Then, I will present our recent progress on
the question "is there a dynamic algorithm with small worst-case update
time" for the spanning forest problem, which is among central problems in
dynamic algorithms on graphs. Our result guarantees an n^{o(1)} worst-case
update time with high probability, where n is the number of nodes. The best
worst-case bounds prior to our work are (i) the long-standing O(\sqrt{n})
bound of [Frederickson STOC'83, Eppstein, Galil, Italiano and Nissenzweig
FOCS'92] (which is slightly improved by a O(\sqrt{\log(n)}) factor by
[Kejlberg-Rasmussen, Kopelowitz, Pettie, Thorup ESA'16]) and (ii) the
polylogarithmic bound of [Kapron, King and Mountjoy SODA'13] which works
under an oblivious adversary assumption (our result does not make such
assumption). The crucial techniques are about expanders: 1) an algorithm
for decomposing a graph into a collection of expanders in near-linear time,
and 2) an algorithm for "repairing" the expansion property of an expander
after deleting some edges of it. These techniques can be of independent
interest.

This talk is based on results by [Nanongkai, Saranurak and Wulff-Nilsen,
FOCS'17], [Nanongkai and Saranurak, STOC'17] and [Wulff-Nilsen, STOC'17].


Host: Yury Makarychev <yury at ttic.edu>


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

On Tue, Jan 9, 2018 at 12:09 PM, Mary Marre <mmarre at ttic.edu> wrote:

> When:     Wednesday, January 10th at *10:30 am *
>
> Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526
>
> Who:       Thatchaphol Saranurak, KTH Royal Institute of Technology
>
>
> Title:        Dynamic Spanning Forest: Techniques and Connections to Other
> Fields
>
> Abstract: I will first give an overview of dynamic algorithms and their
> connections to other fields. Then, I will present our recent progress on
> the question "is there a dynamic algorithm with small worst-case update
> time" for the spanning forest problem, which is among central problems in
> dynamic algorithms on graphs. Our result guarantees an n^{o(1)} worst-case
> update time with high probability, where n is the number of nodes. The best
> worst-case bounds prior to our work are (i) the long-standing O(\sqrt{n})
> bound of [Frederickson STOC'83, Eppstein, Galil, Italiano and Nissenzweig
> FOCS'92] (which is slightly improved by a O(\sqrt{\log(n)}) factor by
> [Kejlberg-Rasmussen, Kopelowitz, Pettie, Thorup ESA'16]) and (ii) the
> polylogarithmic bound of [Kapron, King and Mountjoy SODA'13] which works
> under an oblivious adversary assumption (our result does not make such
> assumption). The crucial techniques are about expanders: 1) an algorithm
> for decomposing a graph into a collection of expanders in near-linear time,
> and 2) an algorithm for "repairing" the expansion property of an expander
> after deleting some edges of it. These techniques can be of independent
> interest.
>
> This talk is based on results by [Nanongkai, Saranurak and Wulff-Nilsen,
> FOCS'17], [Nanongkai and Saranurak, STOC'17] and [Wulff-Nilsen, STOC'17].
>
>
> Host: Yury Makarychev <yury at ttic.edu>
>
>
>
> Mary C. Marre
> Administrative Assistant
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Room 504*
> *Chicago, IL  60637*
> *p:(773) 834-1757 <(773)%20834-1757>*
> *f: (773) 357-6970 <(773)%20357-6970>*
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
>
>
>
> On Fri, Jan 5, 2018 at 3:07 PM, Mary Marre <mmarre at ttic.edu> wrote:
>
>> When:     Wednesday, January 10th at *10:30 am *
>>
>> Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526
>>
>> Who:       Thatchaphol Saranurak, KTH Royal Institute of Technology
>>
>>
>> Title:        Dynamic Spanning Forest: Techniques and Connections to
>> Other Fields
>>
>> Abstract: I will first give an overview of dynamic algorithms and their
>> connections to other fields. Then, I will present our recent progress on
>> the question "is there a dynamic algorithm with small worst-case update
>> time" for the spanning forest problem, which is among central problems in
>> dynamic algorithms on graphs. Our result guarantees an n^{o(1)} worst-case
>> update time with high probability, where n is the number of nodes. The best
>> worst-case bounds prior to our work are (i) the long-standing O(\sqrt{n})
>> bound of [Frederickson STOC'83, Eppstein, Galil, Italiano and Nissenzweig
>> FOCS'92] (which is slightly improved by a O(\sqrt{\log(n)}) factor by
>> [Kejlberg-Rasmussen, Kopelowitz, Pettie, Thorup ESA'16]) and (ii) the
>> polylogarithmic bound of [Kapron, King and Mountjoy SODA'13] which works
>> under an oblivious adversary assumption (our result does not make such
>> assumption). The crucial techniques are about expanders: 1) an algorithm
>> for decomposing a graph into a collection of expanders in near-linear time,
>> and 2) an algorithm for "repairing" the expansion property of an expander
>> after deleting some edges of it. These techniques can be of independent
>> interest.
>>
>> This talk is based on results by [Nanongkai, Saranurak and Wulff-Nilsen,
>> FOCS'17], [Nanongkai and Saranurak, STOC'17] and [Wulff-Nilsen, STOC'17].
>>
>>
>> Host: Yury Makarychev <yury at ttic.edu>
>>
>>
>>
>>
>> Mary C. Marre
>> Administrative Assistant
>> *Toyota Technological Institute*
>> *6045 S. Kenwood Avenue*
>> *Room 504*
>> *Chicago, IL  60637*
>> *p:(773) 834-1757 <(773)%20834-1757>*
>> *f: (773) 357-6970 <(773)%20357-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/20180110/5902c326/attachment.html>