[Turkmath:7632] Hatirlatma: Istanbul Ayrik Matematik Toplantilari Nisan Ayi Seminer Duyurusu

[Türker BIYIKOĞLU]

Hatirlatma:
Istanbul Ayrik Matematik Toplantilari Seminer Duyurusu

Degerli Matematikciler,

Istanbul Ayrik Matematik Toplantilarina bir sure ara verdikten sonra 
Nisan ayi toplantisi herzaman oldugu gibi Istanbul Matematiksel Bilimler 
Merkezinin (IMBM) cok guzel binasinda olucak.
Nisan ayi toplantimiz  15 Nisan Cuma gunu saat 11.00'de
Gunes Ercal (University of California, Los Angeles, USA) "Topics in 
Randomized Algorithms" baslikli bir konusma yapacaktir.

Konusma konusuyla ilgili detaylari asagida ve ekteki ilanda gorebilirsiniz.

Seminer oncesi, saat 10.30'dan itibaren cay-kahve ve kurabiye servisi 
olacaktir. Konusmaya herkes davetlidir.

Turker Biyikoglu  Tinaz Ekim-Asici



I M B M istanbul center for mathematical sciences
Istanbul Discrete Mathematics Meetings

Gunes Ercal
Topics in Randomized Algorithms
University of California, Los Angeles

Abstract

This talk is a general overview of the use of randomization to various 
types of algorithmic problems, particularly of a graph theoretic nature. 
We introduce with some examples on MinCut and MST, illustrating the 
benet of simplicity. We continue with random walk based methods both to 
illustrate complexity bounds for the randomized logspace class, and to 
give intuition for randomized approximation schemes for hard counting 
problems. This brings us to a major open question on whether or not 
there is a gap between randomized logspace and deterministic logspace: 
Namely, to what extent may we derandomize?

Graph theoretic techniques based on expanders are useful throughout these
questions. Finally, we also mention some problems in the distributed 
algorithmic setting where, in one case, a provably exponential gap in 
time complexity exists between randomized and deterministic versions, 
and in another case, literally the deterministic version is impossible 
to solve in general whereas a randomized approach is both possible and 
uncomplicated.


Date: Friday, April 15, 2011
Time: 11:00
Place: IMBM Seminar Room, Bogazici University

Istanbul Matematiksel Bilimler Merkezi hakkinda bilgi icin: 
http://imbm.org.tr/
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: <http://yunus.listweb.bilkent.edu.tr/cgi-bin/mailman/private/turkmath/attachments/20110414/14fd81a0/attachment.htm>