Miklós Ajtai

Die einheimische Form davon persönlichen Namen ist Ajtai Miklós. Dieser Artikel verwendet Westliche Namensordnung bei der Erwähnung von Personen.
Miklos Ajtai
Geboren 2. Juli 1946 (Alter 76)
Budapest, Zweite Republik Ungarn
Staatsangehörigkeit Ungarisch amerikanisch
Alma Mater Ungarische Akademie der Wissenschaften
Auszeichnungen Knuth -Preis (2003)[1]
Wissenschaftliche Karriere
Felder Computerkomplexitätstheorie
Institutionen IBM Almaden Research Center

Miklós Ajtai (geboren am 2. Juli 1946) ist a Informatiker Bei der IBM Almaden Research Center, Vereinigte Staaten. Im Jahr 2003 erhielt er das Knuth -Preis für seine zahlreichen Beiträge auf dem Feld, einschließlich eines Klassiker Sortiernetzwerk Algorithmus (gemeinsam mit J. Komlós und Endre Szemerédi), exponentielle Untergrenzen, superlineare Zeitraum-Kompromisse für Verzweigungen und andere "einzigartige und spektakuläre" Ergebnisse. Er ist Mitglied der USA Nationale Akademie der Wissenschaften.[2]

Ausgewählte Ergebnisse

Einer der Ergebnisse von Ajtai besagt, dass die Länge der Beweise in Aussagelogik des Pigeonhole -Prinzip zum n Gegenstände wachsen schneller als jeder andere Polynom in n. Er hat auch bewiesen, dass die Aussage "zwei beliebte zählbar Strukturen das sind auch äquivalent zweiter Ordnung isomorph" ist beides konsistent mit und unabhängig von ZFC. Ajtai und Szemerédi bewiesen das Ecken Theorem, ein wichtiger Schritt in Richtung höherdimensionaler Verallgemeinerungen der Szemerédi Theorem. Mit Komlós und Szemerédi er bewies das ct2/Protokoll t Obergrenze für die Ramsey -Nummer R(3,t). Die entsprechende Untergrenze wurde nachgewiesen von Kim Erst 1995 ein Ergebnis, das ihm a einbrachte Fulkerson -Preis. Mit Chvátal, Neugeborenes, und SzemerédiAjtai hat das bewiesen Ungleichheit der Zahlenkreuzung, dass jede Zeichnung einer Grafik mit n Eckpunkte und m Kanten, wo m > 4n, hat zumindest m3 / 100n2 Kreuzungen. Ajtai und Dwork 1997 ein Gitterbasis entwickelt öffentlicher Kryptosystem; Ajtai hat umfangreiche Arbeiten angelegt Gitterprobleme. Für seine zahlreichen Beiträge in der theoretischen Informatik erhielt er den Knuth -Preis.[1]

Biodaten

Ajtai erhielt seine Kandidat der Wissenschaften Abschluss im Jahr 1976 von der Ungarische Akademie der Wissenschaften.[3] Seit 1995 ist er externes Mitglied der Ungarische Akademie der Wissenschaften.

1998 war er ein eingeladener Redner der Internationaler Kongress der Mathematiker in Berlin.[4] 2012 wurde er als gewählt als Fellow der American Association for the Advancement of Science.[5] Im Jahr 2021 wurde er zum Mitglied der National Academy of Sciences gewählt.[6]

Literaturverzeichnis

  • Ajtai, Miklós (10. Mai 2008). "Optimale Untergrenzen für die Korkine-Zolotareff-Parameter eines Gitters und für Schnorr-Algorithmus für das kürzeste Vektorproblem". Theorie des Computers. 4: 21–51. doi:10.4086/toc.2008.v004a002.
  • Ajtai, Miklós (5. Oktober 2005). "Eine nichtlineare Zeit unter den Booleschen Verzweigungsprogrammen". Theorie des Computers. 1: 149–176. doi:10.4086/toc.2005.v001a008.
  • Ajtai, M. (1996). "Harte Instanzen von Gitterproblemen erzeugen (erweitertes Zusammenfassung)". Verfahren des achtundzwanzigsten jährlichen ACM -Symposiums über die Theorie des Computers - STOC '96. S. 99–108. doi:10.1145/237814.237838. ISBN 978-0-89791-785-8. S2CID 6864824.

Ausgewählte Papiere

  1. Ajtai, M. (September 1979). "Isomorphismus und Äquivalenz höherer Ordnung". Annalen der mathematischen Logik. 16 (3): 181–203. doi:10.1016/0003-4843 (79) 90001-9.
  2. Ajtai, M.; Komlós, J.; Szemerédi, E. (März 1982). "Größte zufällige Komponente von a k-Würfel". Combinatorica. 2 (1): 1–7. doi:10.1007/bf02579276. S2CID 7903662.

Verweise

  1. ^ a b "Archivierte Kopie". Archiviert von das Original am 2021-05-14. Abgerufen 2015-02-10.{{}}: CS1 Wartung: Archiviertes Kopie als Titel (Link)
  2. ^ "Nachrichten von der National Academy of Sciences". 26. April 2021. Abgerufen 1. Juli 2021. Neu gewählte Mitglieder und ihre Zugehörigkeiten zum Zeitpunkt der Wahl sind: ... Ajtai, Miklós; IBM Emeritusforscher, IBM Almaden Research Center, Los Gatos, Kalifornien.
  3. ^ Magyar Tudományos Akadémia, Almanach, 1986, Budapest.
  4. ^ Ajtai, Miklós (1998). "Worst-Case-Komplexität, durchschnittliche Komplexität und Gitterprobleme". Documenta Mathematica: 421–428.
  5. ^ AAAS -Mitglieder wurden als Stipendiaten gewählt, AAAS, 29. November 2012
  6. ^ "Die National Academy of Sciences wählt neue Mitglieder - darunter eine Rekordzahl von Frauen - und internationalen Mitgliedern". Nasonline.org. 26. April 2021. Abgerufen 28. April 2021.

Externe Links