Miklós Ajtai

Den inhemska formen av detta personnamn är Ajtai Miklós . Den här artikeln använder västerländsk namnordning när individer nämns.

Miklos Ajtai
Född	( 1946-07-02 ) 2 juli 1946 Budapest , andra republiken Ungern
Nationalitet	Ungersk-amerikansk
Alma mater	Ungerska vetenskapsakademin
Utmärkelser	Knuth-priset (2003)
Vetenskaplig karriär
Fält	Beräkningskomplexitetsteori
institutioner	IBM Almaden Research Center

Miklós Ajtai (född 2 juli 1946) är en datavetare vid IBM Almaden Research Center, USA. 2003 fick han Knuth-priset för sina många bidrag till området, inklusive en klassisk sorteringsnätverksalgoritm (utvecklad tillsammans med J. Komlós och Endre Szemerédi ), exponentiella nedre gränser, superlinjära tid-rum-avvägningar för förgreningsprogram och andra " unika och spektakulära" resultat. Han är medlem av US National Academy of Sciences .

Valda resultat

Ett av Ajtais resultat säger att längden på bevis i propositionell logik för duvhålsprincipen för n poster växer snabbare än något polynom i n . Han bevisade också att påståendet "alla två räknebara strukturer som är andra ordningens ekvivalenter också är isomorfa " är både överensstämmande med och oberoende av ZFC . Ajtai och Szemerédi bevisade hörnsatsen , ett viktigt steg mot högre dimensionella generaliseringar av Szemerédi-satsen . Med Komlós och Szemerédi bevisade han ct ² /log t övre gränsen för Ramsey-talet R (3, t ). Motsvarande nedre gräns bevisades av Kim först 1995, ett resultat som gav honom ett Fulkerson-pris . Med Chvátal , Newborn och Szemerédi bevisade Ajtai korsningstalets olikhet , att varje ritning av en graf med n hörn och m kanter, där m > 4 n , har minst m ³ / 100 n ² korsningar . Ajtai och Dwork utvecklade 1997 ett gitterbaserat kryptosystem med offentlig nyckel ; Ajtai har gjort ett omfattande arbete med gallerproblem . För sina många insatser inom teoretisk datavetenskap fick han Knuth-priset.

Bio data

Ajtai fick sin kandidatexamen för vetenskaper 1976 från Ungerska vetenskapsakademin . Sedan 1995 har han varit extern ledamot av Ungerska vetenskapsakademin .

1998 var han en inbjuden talare för den internationella matematikkongressen i Berlin. 2012 valdes han till Fellow i American Association for the Advancement of Science . 2021 valdes han till medlem av National Academy of Sciences.

Bibliografi

• Ajtai, Miklós (10 maj 2008). "Optimala nedre gränser för Korkine-Zolotareff-parametrarna för ett gitter och för Schnorrs algoritm för det kortaste vektorproblemet". Theory of Computing . 4 : 21–51. doi : 10.4086/toc.2008.v004a002 .
• Ajtai, Miklós (5 oktober 2005). "En icke-linjär tidsnedre gräns för booleska förgreningsprogram". Theory of Computing . 1 : 149-176. doi : 10.4086/toc.2005.v001a008 .
•    Ajtai, M. (1996). "Genererar hårda instanser av gallerproblem (Utökad abstrakt)". Proceedings från det tjugoåttonde årliga ACM-symposiet om teorin om datorer - STOC '96 . s. 99–108. doi : 10.1145/237814.237838 . ISBN 978-0-89791-785-8 . S2CID 6864824 .

Utvalda papper

1. Ajtai, M. (september 1979). "Isomorfism och högre ordnings ekvivalens" . Annals of Mathematical Logic . 16 (3): 181–203. doi : 10.1016/0003-4843(79)90001-9 .
2.   Ajtai, M.; Komlós, J.; Szemerédi, E. (mars 1982). "Största slumpmässiga komponenten i en k -kub". Combinatorica . 2 (1): 1–7. doi : 10.1007/BF02579276 . S2CID 7903662 .

externa länkar

• Miklós Ajtais hemsida
• Miklós Ajtai -publikationer indexerade av Microsoft Academic
• Miklós Ajtai vid Mathematics Genealogy Project