Ajtai Miklós (matematikus)
 |
Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye. |
| Ajtai Miklós | |
| Született | 1946. július 2. (78 éves) Budapest |
| Állampolgársága | magyar |
| Szülei | Ajtai Miklós (politikus) Radics Ilona vegyész, bölcsészdoktor (1912–1965) |
| Foglalkozása | matematikus |
| Iskolái | Eötvös Loránd Tudományegyetem (–1976, PhD) |
| Kitüntetései |
|
Ajtai Miklós (Budapest, 1946. július 2. –) magyar származású amerikai matematikus, informatikus az amerikai IBM Almaden Research Centerben, a Magyar Tudományos Akadémia külső tagja. 2003-ban az informatika területén elért számos eredményéért – mint amilyen egy klasszikus rendezőhálózati (sorting network) algoritmus (Komlós Jánossal és Szemerédi Endrével), az exponenciális alsó korlátok, a programelágazások szuperlineáris idő-tér hatékonysága és más „egyedi és különleges” munkái – Knuth-díjat kapott.
Életrajza
Ajtai Miklós politikus és Radics Ilona vegyész, bölcsészdoktor (1912–1965) fia. 1976-ban szerezte meg a kandidátusi címet az MTA-n.[2] 1995 óta az Akadémia külső tagja. 1988-ban a berlini Nemzetközi Matematikai Kongresszuson meghívott előadóként vett részt.[3] 2012-ben az American Assotiation for the Advancement of Science (AAAS, Amerikai Tudományfejlesztési Egyesület) tagjának választották.[4] 2021-ben tagja lett a National Academy of Sciences-nek (az egyesült államokbeli tudományos akadémia).[5]
Kutatási területe
Matematikai logikával, számítógéptudománnyal, kombinatorikával foglalkozik.
Eredményei
- Belátta, hogy az az állítás, hogy két másodrendben elemien ekvivalens struktúra izomorf is, független a halmazelmélet szokásos axiómáitól.
- Megmutatta, hogy a skatulyaelvnek nincs polinomiális hosszúságú bizonyítása.
- Igazolta, hogy egy hosszúságú 0-1 sorozatban található egyesek számának paritása nem dönthető el korlátos mélységű és -ben polinomiális méretű hálózattal.
- Komlós Jánossal és Szemerédi Endrével bebizonyította az Ramsey-számokra a felső becslést.
- Szintén Komlós Jánossal és Szemerédi Endrével igazolta, hogy egy pontot és élt tartalmazó véletlen gráf majdnem biztosan tartalmaz egy hosszú utat, ahol értéke -tól függ ().
- 1996-ban megalkotta az első hálóalapú („lattice based”) nyilvános kulcsú titkosítórendszer elméletét, mely a matematikai csoportelméletben található hálókra épül (mely problémák nehézségét Cynthia Dwork-kel közösen elemezték), mely egyike az ígéretes posztkvantum kriptográfiai eljárásoknak, vagyis azoknak, melyek a kvantumszámítógép elterjedésével sem válnak könnyen visszafejthetővé.
Elismerései
- Az MTA külső tagja (1995)
- Knuth-díj (2003) Az elméleti számítógéptudomány terén elért számos eredményéért.
Kapcsolódó szócikkek
Jegyzetek
- ↑ https://www.aaas.org/news/aaas-members-elected-fellows-1
- ↑ (1986) „Almanach”, Kiadó: Magyar Tudományos Akadémia.
- ↑ (1998) „Worst-case complexity, average-case complexity and lattice problems.” (English nyelven). Documenta Mathematica, 421–428. o.
- ↑ AAAS Members Elected as Fellows (English nyelven), 2012. november 29.
- ↑ National Academy of Sciences Elects New Members — Including a Record Number of Women — and International Members (English nyelven). nasonline.org , 2021. április 26. (Hozzáférés: 2021. április 24.)
