Salil Vadhan - Salil Vadhan
 | Bu tirik odamning tarjimai holi qo'shimcha kerak iqtiboslar uchun tekshirish. (2010 yil yanvar) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling) |
Salil Vadhan | |
|---|---|
 Salil Vadhan | |
| Fuqarolik | Qo'shma Shtatlar |
| Olma mater | Garvard universiteti (BA) Massachusets texnologiya instituti (DPhil) |
| Mukofotlar | |
| Ilmiy martaba | |
| Maydonlar | Hisoblash murakkabligi nazariyasi, Kriptografiya |
| Institutlar | Garvard universiteti |
| Doktor doktori | Shafi Goldwasser |
Salil Vadhan Viki Jozef Kompyuter fanlari va amaliy matematika professori Garvard universiteti.[1] 1995 yilda Garvardda matematika va kompyuter fanlari bakalavrini tugatgandan so'ng, u amaliy matematika bo'yicha doktorlik dissertatsiyasini Massachusets texnologiya instituti 1999 yilda, uning maslahatchisi bo'lgan Shafi Goldwasser.[2] Uning tadqiqot markazlari orasidagi interfeys atrofida hisoblash murakkabligi nazariyasi va kriptografiya. U yolg'on tasodifiylik va nolinchi bilimlarni isbotlash mavzulariga e'tibor qaratadi. Uning ishi zig-zag mahsuloti, bilan Omer Rayngold va Avi Uigderson, 2009 yilda bekor qilindi Gödel mukofoti.[3]
Hissa
Kengaytiruvchi grafikalarni qurish uchun zig-zag grafik mahsuloti
Uning ishining asosiy hissalaridan biri - bu yangi turdagi grafika mahsulotidir zig-zag mahsuloti.
Kichik grafika bilan katta grafika mahsulotini olsak, hosil bo'lgan grafika (taxminan) kattaligidan, uning darajasidan kichikigacha va ikkalasidan ham kengayish xususiyatlarini meros qilib oladi. Takrorlash har bir o'lchamdagi doimiy doimiy kengaytirgichlarning oddiy aniq konstruktsiyalarini beradi, bitta doimiy o'lchamdagi kengaytiruvchidan.
Zig-zag mahsulotining sezgi va sodda tahlili uchun juda muhim bo'lib, kengaytiruvchilarni "entropiya to'lqini" targ'ibotchisi vazifasini bajaradigan funktsiyalar deb hisoblashlari mumkin - ular entropiya bir sohada to'plangan ehtimollik taqsimotlarini ushbu kontsentratsiya bo'lgan taqsimotlarga aylantiradi. tarqaldi. Shu nuqtai nazardan, grafik mahsulot bunday ikkita to'lqinning konstruktiv aralashuvini beradi.
Ushbu mahsulotning bir varianti ekstraktorlarga qo'llanilishi mumkin, bu urug'ning uzunligi (manbaning entropiya etishmovchiligiga) logaritmik ravishda bog'liq bo'lgan va yuqori min-entropiyaning deyarli barcha entropiyasini chiqaradigan birinchi aniq ekstraktorlarga beriladi. manbalar. Ushbu yuqori min-entropiya ekstraktorlari bir nechta qiziqarli dasturlarga, shu jumladan, birinchi darajali aniq kengaytiruvchilarga, "o'zaro bog'liqlik chegarasini" engishadi.
Vadhan yana bir soddalashtirilgan yondashuvni taklif qildi[4] yo'naltirilmaganlarga ST-ulanish Reingoldning yutuqlaridan so'ng muammo, shuningdek zig-zag mahsuloti foydali bo'ldi Omer Rayngold buni isboti SL =L.
Nolinchi ma'lumotni tasdiqlovchi dalillar
Uning bu sohadagi faoliyati murakkablik-nazariy usullardan foydalanib, nolinchi bilimlarni isbotlashning kuchi va cheklovlarini tushunadi. Bilan bir qator hujjatlarda Oded Goldreich va Amit Sahai, ular SZK sinfini statistik nolinchi ma'lumotlarga ega bo'lgan muammolarni chuqur tushunib oldilar, SZK sinfini tavsifladilar va SZK har xil operatsiyalar ostida yopiqligini isbotladilar. Yaqinda uning ishi SZK sinfining chegaralaridan tashqarida nol-bilimlarni isbotlash ustida ishlashga urindi.
Tasodifiy ekstraktorlar
Lu bilan, Omer Rayngold va Avi Uigderson, u birinchi qurilishini berdi tasodifiy ekstraktorlar bu "doimiy omillarga qadar optimal" bo'lib, mavzu bo'yicha o'n yillik ishda muhim bosqichga erishdi.
Trevisan, Tsukerman, Kamp va Rao bilan u (noma'lum) samarali algoritm tomonidan ishlab chiqarilgan tasodifiy manbalar bo'lgan namunali manbalardan tasodifiylikni olish (va ma'lumotlarni siqishni) nazariyasini ishlab chiqdi.
E'tirof etish
Vadhan sifatida saylandi ACM Fellow 2018 yilda "hisoblash murakkabligi va kriptografiyani takomillashtirish va nazariy kompyuter fanlarini jamoat tomonidan qo'llab-quvvatlash uchun".[5]
Adabiyotlar
- ^ Garvard fakulteti ma'lumotnomasi.
- ^ Salil Vadhan da Matematikaning nasabnomasi loyihasi.
- ^ 2009 yil Gödel mukofoti, Nazariy kompyuter fanlari bo'yicha Evropa assotsiatsiyasi.
- ^ Rozenman-Vadan.
- ^ Raqamli asrni qo'llab-quvvatlovchi muhim yutuqlar uchun 2018 yil ACM stipendiyalari, Hisoblash texnikasi assotsiatsiyasi, 2018 yil 5-dekabr
