Ajtai Miklós (matematikus)

Ez a szócikk a matematikusról szól. Hasonló címmel lásd még: Ajtai Miklós (egyértelműsítő lap).

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 (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 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]

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

• 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 ${\displaystyle n}$ hosszúságú 0-1 sorozatban található egyesek számának paritása nem dönthető el korlátos mélységű és ${\displaystyle n}$-ben polinomiális méretű hálózattal.
• Komlós Jánossal és Szemerédi Endrével bebizonyította az ${\displaystyle R(3,n)}$ Ramsey-számokra a ${\displaystyle cn^{2}/\log n}$ felső becslést.
• Szintén Komlós Jánossal és Szemerédi Endrével igazolta, hogy egy ${\displaystyle n}$ pontot és ${\displaystyle an}$ élt tartalmazó véletlen gráf majdnem biztosan tartalmaz egy ${\displaystyle cn}$ hosszú utat, ahol ${\displaystyle c}$ értéke ${\displaystyle a}$-tól függ (${\displaystyle a>1/2}$).
• 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é.

• 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.

• A Magyar Tudományos Akadémia tagjainak listája (A–F)