Miklós Ajtai - Miklós Ajtai

Nativní forma tohoto osobní jméno je Ajtai Miklós. Tento článek používá Pořadí západních jmen když se zmiňuji o jednotlivcích.
Miklos Ajtai
narozený (1946-07-02) 2. července 1946 (věk 74)
Budapešť, Druhá maďarská republika
NárodnostMaďarsko-americký
Alma materMaďarská akademie věd
OceněníKnuth Prize (2003)[1]
Vědecká kariéra
PoleTeorie výpočetní složitosti
InstituceIBM Výzkumné centrum Almaden

Miklós Ajtai (narozen 2. července 1946) je a počítačový vědec na IBM Výzkumné centrum Almaden, Spojené státy. V roce 2003 obdržel Knuth Prize za jeho četné příspěvky do oboru, včetně klasiky třídicí síť algoritmus (vyvinutý společně s J. Komlós a Endre Szemerédi ), exponenciální dolní hranice, superlineární časoprostorové kompromisy pro větvicí programy a další „jedinečné a velkolepé“ výsledky.

Vybrané výsledky

Jeden z výsledků Ajtai uvádí, že délka důkazů v výroková logika z princip pigeonhole pro n položky rostou rychleji než kdokoli jiný polynomiální v n. Rovněž dokázal, že prohlášení „jakékoli dva počitatelný struktur které jsou ekvivalentem druhého řádu jsou také izomorfní „je obojí konzistentní s a nezávislý z ZFC. Ajtai a Szemerédi prokázal věta o rozích, důležitý krok k vyšší dimenzionální generalizaci Szemerédiho věta. S Komlós a Szemerédi prokázal ct2/ log t horní hranice pro Ramseyovo číslo R(3,t). Odpovídající dolní mez byla prokázána Kim teprve v roce 1995, výsledek, který mu vynesl a Fulkersonova cena. S Chvátal, Novorozený, a Szemerédi, Ajtai prokázal nerovnost křížení čísel, že jakýkoli výkres grafu s n vrcholy a m hrany, kde m > 4n, má alespoň m3 / 100n2 přechody. Ajtai a Dwork vymyslel v roce 1997 mřížový základ kryptosystém veřejného klíče; Ajtai odvedl rozsáhlou práci mřížkové problémy. Za četné příspěvky v teoretické informatice získal Knuthovu cenu.[1]

Biodata

Ajtai přijal jeho Kandidát věd stupně v roce 1976 z Maďarská akademie věd.[2] Od roku 1995 je externím členem Maďarská akademie věd.

V roce 1998 byl pozvaným mluvčím Mezinárodní kongres matematiků v Berlíně.[3] V roce 2012 byl zvolen jako Člen Americké asociace pro pokrok ve vědě.[4]

Bibliografie

  • Ajtai, Miklos: Optimální dolní meze Korkine-Zolotareffových parametrů mřížky a pro Schnorrův algoritmus pro nejkratší vektorový problém, in: Theory of Computering, Vol. 4, ppp 21-51.[5]
  • Ajtai, Miklos: Nelineární časová hranice pro booleovské větvicí programy, in: Theory of Computering, Vol. 1, s. 149-176.[5]
  • Ajtai, Miklos: Generování těžkých instancí mřížových problémů. Elektronické kolokvium o výpočetní úplnosti, s. 1-29.[6]

Vybrané příspěvky

  1. Ajtai, M. (1979), „Izomorfismus a ekvivalence vyššího řádu“, 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. (1982), „Největší náhodná složka a k-krychle", Combinatorica, 2 (1): 1–7, doi:10.1007 / BF02579276.

Reference

  1. ^ A b http://www.sigact.org/Prizes/Knuth/2003.html
  2. ^ Magyar Tudományos Akadémia, Almanach, 1986, Budapešť.
  3. ^ Ajtai, Miklós (1998). „Nejhorší složitost, průměrná složitost a mřížkové problémy“. Doc. Matematika. (Bielefeld) Extra sv. ICM Berlin, 1998, roč. III. 421–428.
  4. ^ Členové AAAS zvolení za členy, AAAS, 29. listopadu 2012
  5. ^ A b „Články od Miklóse Ajtaiho“. Teorie výpočtu. Citováno 23. října 2019.
  6. ^ „Generování těžkých instancí mřížových problémů“ (PDF). semanticscholar.org. Citováno 23. října 2019.

externí odkazy