Ajtai Miklós (matematikus)

Sablon:Egyért2 Sablon:Nincs forrás Sablon:Személy infobox 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 $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 $n$-ben polinomiális méretű hálózattal.
• Komlós Jánossal és Szemerédi Endrével bebizonyította az $R(3,n)$ Ramsey-számokra a $c{n}^2/\log n$ felső becslést.
• Szintén Komlós Jánossal és Szemerédi Endrével igazolta, hogy egy $n$ pontot és $an$ élt tartalmazó véletlen gráf majdnem biztosan tartalmaz egy $cn$ hosszú utat, ahol $c$ értéke $a$-tól függ ($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é.

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)