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. 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. 2012-ben az American Assotiation for the Advancement of Science (AAAS, Amerikai Tudományfejlesztési Egyesület) tagjának választották. 2021-ben tagja lett a National Academy of Sciences-nek (az egyesült államokbeli tudományos akadémia).
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 A Magyar Tudományos Akadémia tagjainak listája (A–F)
Jegyzetek
Kategória:Amerikai matematikusok Kategória:Magyar matematikusok Kategória:MTA-tagok Kategória:Magyar emigránsok az Amerikai Egyesült Államokban Kategória:1946-ban született személyek Kategória:Budapesten született személyek Kategória:Élő személyek