Ajtai Miklós (matematikus)

(1946) magyar származású amerikai matematikus, az MTA külső tagja

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.

Ajtai Miklós
Született1946. július 2. (77 éves)
Budapest
Állampolgárságamagyar
SzüleiAjtai Miklós (politikus) Radics Ilona vegyész, bölcsészdoktor (1912–1965)
Foglalkozásamatematikus
IskoláiEötvös Loránd Tudományegyetem (–1976, PhD)
Kitüntetései
  • Knuth-díj (2003)
  • Fellow of the American Association for the Advancement of Science (2012)[1]

SablonWikidataSegítség

Életrajza

szerkesztés

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

szerkesztés

Matematikai logikával, számítógéptudománnyal, kombinatorikával foglalkozik.

Eredményei

szerkesztés
  • 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

szerkesztés
  • 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

szerkesztés
  1. https://www.aaas.org/news/aaas-members-elected-fellows-1
  2. (1986) „Almanach”, Kiadó: Magyar Tudományos Akadémia.  
  3. (1998) „Worst-case complexity, average-case complexity and lattice problems.” (angol nyelven). Documenta Mathematica, 421–428. o.  
  4. AAAS Members Elected as Fellows (angol nyelven), 2012. november 29.
  5. National Academy of Sciences Elects New Members — Including a Record Number of Women — and International Members (angol nyelven). nasonline.org , 2021. április 26. (Hozzáférés: 2021. április 24.)