Efsane Bilgisayar Bilimci Prof. Rusins Freivalds'ın Boğaziçi'ndeki Semineri

0
FZ
Boğaziçi Üniversitesi Bilgisayar Mühendisliği bölümünden Prof. Cem Say bildiriyor:

"Letonya Bilimler Akademisi üyesi ünlü TCS'cı Rusins Freivalds (1975'te olasılıksal algoritmaların deterministik olanlara bir üstünlüğü olduğunun ilk ispatını yaptı, 1981'de sonlu bellekli ve "az hatalı" olasılıksal makinelerin sonlu bellekli deterministik makinelerden daha güçlü olduğunu ispatladı, state sayısı avantajının boyutunu da daha yeni ispatlamış görünüyor,) 17 Kasım Pazartesi günü bölümümüzü ziyaret edecek, sanırım saat 14'te de bir seminer verecek (özet aşağıda). Davetlisiniz."
Nonconstructive methods in finite automata

Rusins Freivalds
(University of Latvia)

A.Ambainis and R.Freivalds proved in 1998 that for recognition of some languages quantum finite automata can have smaller number of states than deterministic ones, and this difference can even be exponential. The proof contained a slight non-constructiveness, and the exponent was not shown explicitly. For probabilistic finite automata, the exponentiality of such a distinction was not yet proved. The best (smaller) gap was proved by Ambainis in 1996. The languages considered by Ambainis/Freivalds were presented explicitly, but the exponent was not. In a very recent paper by R.Freivalds the non-constructiveness is modified, and an explicit (and seemingly much better) exponent is obtained at the expense of having only non-constructive description of the languages used.

Moreover, the best estimate proved in this paper is proved under assumption of the well-known Artin's Conjecture (1927) in Number Theory. The paper contains also a theorem that does not depend on any open conjectures but the estimate is worse, and the description of the languages used is even less constructive. This seems to be the first result in finite automata depending on open conjectures in Number Theory.

Görüşler

0
oetzi_
Seminer saati ve yerini kesinleştirebilir misiniz.
Görüş belirtmek için giriş yapın...

İlgili Yazılar

1. Türkiye Fantezi ve Bilimkurgu Etkinliği

larweda

24 Haziran 2001 (bugün :-)) saat 12:00`da İstanbul Bilgi Üniversitesi`nde 1.nci Türkiye Fantezi ve Bilimkurgu Etkinliği "Fikir Rönesansı" gerçekleştirilecek. İthaki, Metis ve Ankira yayınevinin desteğiyle gerçekleştirilecek olan etkinlik, BK ve Fantezi edebiyatı hakkında seminerler, söyleşiler ve ufak bir film gösterisini içeriyor. Detaylı bilgi.

LKD sunar: Uludağ semineri

loker

02 Nisan Cumartesi günü Ulusal Dağıtım
projesinden Barış Metin 13:30'da EMO İstanbul Şubesi'nde bir seminer verecek. Katılım herkese açık.

Linux Semineri : Sanal Özel Ağ Sunucuları (VPN)

anonim

Linux Kullanıcıları Derneği, 7 Haziran Cumartesi günü İstanbul'da bir linux semineri düzenliyor. 15:00'de başlayacak seminerde, sanal özel ağ sunucularının (VPN) mimarileri, kullanım amaçları ve Linux üzerinde sunulabilecek çözümleri anlatılıyor. Özgür sanal özel ağ sunucuları arasında yer alan FreeSWan, PoPToP ve OpenVPN'e değinilecek ve alternatif çözümler tartışılacak. -Ayrıntılı Bilgi-

15 Mart, Fatih Üniversitesi, Linux Semineri

hcg

Fatih Üniversitesi Kariyer Kulübü ve LKD Seminer Çalışma Grubu ortak çalışması. Kariyer Günleri kapsamında, 15 Mart Pazartesi günü, 11.30-13.00 arasında, Fatih Üniv. D Blok Konferans Salonunda, Enver Altın tarafından "Linux'u ne kadar tanıyoruz?" başlıklı bir seminer verilecek.

İlgilenen herkes davetlidir.

400 saniyelik tasarım ve teknoloji sunumları

anonim

Mimarlık, moda, fotoğraf, video, grafik, endüstriyel, Internet, ve medya teknolojileri alanlarından ondört tasarımcı buluşuyor. Her biri 400 saniyelik sunumlar yapacak.

Difuzyon.org tarafından düzenlenen bu seri etkinliklerde İstanbul’da tasarım adı altında yapılan işlerin görüntülenmesi, sunulması, ve tartışılması amaçlıyor. Buluşma bugün (Perşembe) akşam 19:00 da şurada olacak.