Miklós Ajtai

Miklós Ajtai

Miklós Ajtai (* 2. Juli 1946 in Budapest) ist ein ungarischer Informatiker.

Ajtai wurde 1976 an der Loránd-Eötvös-Universität bei Andras Hajnal promoviert und lehrte dann selbst an der Universität. Er ist Wissenschaftler am IBM Almaden Research Center in San Jose.

Ajtai beschäftigt sich insbesondere mit Komplexitätstheorie, Kombinatorik und Mathematischer Logik. Außerdem beschäftigte er sich mit Kryptographie ausgehend von seiner Untersuchung von Gitterproblemen und deren Berechnungsschwierigkeit. Weitere Forschungsfelder sind Sortierung, endliche Modelltheorie, Expander Graphen, deterministische Simulation probabilistischer Algorithmen. Besondere Bedeutung für die Komplexitätstheorie und die Kryptographie erlangte 1996 seine Konstruktion von Zahlengittern, bei denen es im durchschnittlichen Fall genau so schwer ist, ihren kürzesten Vektor bezüglich seiner Länge zu approximieren (bis auf einen polynomialen Faktor in der Dimension des Gitters), wie im schwierigsten Fall.[1]

Ajtai ist seit 1995 auswärtiges Mitglied der Ungarischen Akademie der Wissenschaften. 2003 erhielt er den Knuth-Preis.

Einzelnachweise

  1. ↑ Generating hard instances of lattice problems (extended abstract). Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (STOC '96), AMS 1996, S. 99–108

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Miklós Ajtai — Miklos Ajtai Born 2 July 1946 Budapest, Second Republic of Hungary Residence San Jose, California, United States of America …   Wikipedia

  • Miklós Ajtai — Nacimiento 2 de junio, 1946 Budapest,  Hungría Nacionalidad Húngara Cam …   Wikipedia Español

  • Miklós Ajtai — (2 juillet 1946, Budapest, Hongrie ) est un chercheur en informatique au IBM Almaden Research Center. En 2003, il reçoit le prix Knuth pour ses nombreuses contributions au domaine, notamment un algorithme de tri par réseau, développé avec János… …   Wikipédia en Français

  • Lattice problem — In computer science, lattice problems are a class of optimization problems on lattices. The conjectured intractability of such problems is central to construction of secure lattice based cryptosystems. For applications in such cryptosystems,… …   Wikipedia

  • Премия Кнута — Гэри Миллер вручает премию 2008 года Фолькеру Штрассену Премия Кнута (англ.  …   Википедия

  • Knuth Prize — Gary Miller presents Volker Strassen with the 2008 Knuth Prize at SODA 2009. The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth. Contents …   Wikipedia

  • Corners theorem — In mathematics, the corners theorem is an important result, proved by Miklós Ajtai and Endre Szemerédi, of a statement in arithmetic combinatorics. It states that for every ε > 0 there exists N such that given at least εN2 points in… …   Wikipedia

  • Covering problem of Rado — The covering problem of Rado is an unsolved problem in geometry concerning covering planar sets by squares. It was formulated in 1928 by Tibor Radó and has been generalized to more general shapes and higher dimensions by Richard Rado. Formulation …   Wikipedia

  • Combinatorica — is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors in chief with Paul Erdős as honorary editor in chief. The… …   Wikipedia

  • List of people by Erdős number — Paul Erdős was one of the most prolific writers of mathematical papers. He collaborated a great deal, having 511 joint authors, a number of whom also have many collaborators. The Erdős number measures the collaborative distance between an author… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”