Miklós Ajtai

Rodzima forma tego imienia to Ajtai Miklós . W tym artykule przy wymienianiu osób zastosowano zachodnią kolejność imion .

Miklos Ajtai
Urodzić się	( 02.07.1946 ) 2 lipca 1946 Budapeszt , Druga Republika Węgierska
Narodowość	Węgiersko-amerykański
Alma Mater	Węgierska Akademia Nauk
Nagrody	Nagroda Knutha (2003)
Kariera naukowa
Pola	Teoria złożoności obliczeniowej
Instytucje	Centrum badawcze IBM Almaden

Miklós Ajtai (ur. 2 lipca 1946) jest informatykiem w Centrum Badawczym IBM Almaden w Stanach Zjednoczonych. W 2003 roku otrzymał nagrodę Knutha za liczne zasługi w tej dziedzinie, w tym klasyczny algorytm sieci sortowania (opracowany wspólnie z J. Komlósem i Endre Szemerédim ), wykładnicze dolne granice, superliniowe kompromisy czasoprzestrzenne dla programów rozgałęziających i inne „ wyjątkowe i spektakularne” rezultaty. Jest członkiem Amerykańskiej Narodowej Akademii Nauk .

Wybrane wyniki

Jeden z wyników Ajtai stwierdza, że ​​długość dowodów w logice zdań zasady przegródek dla n pozycji rośnie szybciej niż jakikolwiek wielomian w n . Udowodnił również, że stwierdzenie „dowolne dwie policzalne struktury , które są równoważne drugiego rzędu, są również izomorficzne ” jest zarówno zgodne , jak i niezależne od ZFC . Ajtai i Szemerédi udowodnili twierdzenie o rogach twierdzenia Szemerédiego na wyższe wymiary . Wraz z Komlósem i Szemerédim udowodnił górną granicę ct ² /log t dla liczby Ramseya R (3, t ). Odpowiednią dolną granicę Kim udowodnił dopiero w 1995 roku, co przyniosło mu nagrodę Fulkersona . Z Chvátalem , Newbornem i Szemerédim , Ajtai udowodnił przecinająca się nierówność liczbowa , że dowolny rysunek grafu o n wierzchołkach i m krawędziach, gdzie m > 4 n , ma co najmniej m ³ / 100 n ² przecięć . Ajtai i Dwork opracowali w 1997 roku kryptosystem klucza publicznego oparty na sieci ; Ajtai wykonał obszerną pracę nad problemami sieciowymi . Za liczne zasługi w dziedzinie informatyki teoretycznej otrzymał nagrodę Knutha.

Dane biologiczne

Ajtai otrzymał stopień kandydata nauk w 1976 roku z Węgierskiej Akademii Nauk . Od 1995 jest członkiem zewnętrznym Węgierskiej Akademii Nauk .

W 1998 był zaproszonym mówcą Międzynarodowego Kongresu Matematyków w Berlinie. W 2012 roku został wybrany na członka Amerykańskiego Stowarzyszenia Postępu Nauki . W 2021 został wybrany członkiem Narodowej Akademii Nauk.

Bibliografia

• Ajtai, Miklos (10 maja 2008). „Optymalne dolne granice parametrów siatki Korkine'a-Zolotarefa i algorytmu Schnorra dla problemu najkrótszego wektora”. Teoria informatyki . 4 : 21–51. doi : 10.4086/toc.2008.v004a002 .
• Ajtai, Miklós (5 października 2005). „Nieliniowa dolna granica czasu dla programów rozgałęzień boolowskich”. Teoria informatyki . 1 : 149–176. doi : 10.4086/toc.2005.v001a008 .
•    Ajtai, M. (1996). „Generowanie twardych przypadków problemów z kratą (rozszerzone streszczenie)” . Materiały z dwudziestego ósmego dorocznego sympozjum ACM na temat teorii obliczeń - STOC '96 . s. 99–108. doi : 10.1145/237814.237838 . ISBN 978-0-89791-785-8 . S2CID 6864824 .

Wybrane artykuły

1. Ajtai, M. (wrzesień 1979). „Izomorfizm i równoważność wyższego rzędu” . Roczniki logiki matematycznej . 16 (3): 181–203. doi : 10.1016/0003-4843(79)90001-9 .
2.   Ajtai, M.; Komlos, J.; Szemerédi, E. (marzec 1982). „Największy losowy składnik k -sześcianu ”. Kombinatoryka . 2 (1): 1–7. doi : 10.1007/BF02579276 . S2CID 7903662 .

Linki zewnętrzne

• Strona główna Miklósa Ajtai
• Miklósa Ajtai indeksowane przez Microsoft Academic
• Miklós Ajtai w Mathematics Genealogy Project