Michael Sipser

Michael Sipser

Michael Fredric Sipser ist ein US-amerikanischer Informatiker.

Sipser studierte Mathematik an der Cornell University (Bachelor 1974) und wurde 1980 an der University of California, Berkeley bei Manuel Blum in Informatik promoviert (Nondeterminism and the Size of Two-Way Finite Automata). Er ist Professor für Angewandte Mathematik am Massachusetts Institute of Technology, wo er seit 1980 ist und 1998 bis 2000 Vorstand der Fakultät für Angewandte Mathematik war und seit 2004 Vorstand der Fakultät für Mathematik ist. 1980 war er in der Forschung bei IBM, 1985/96 war er Gastwissenschaftler in Berkeley und 1988 an der Hebräischen Universität (als Lady Davis Fellow).

Sipser beschäftigt sich mit Komplexitätstheorie, worüber er ein Standardwerk[1] schrieb, mit Interaktiven Beweissystemen, Algorithmen, Quanteninformatik und effizienten fehlerkorrigierenden Codes. 1978 bewies er mit David Lichtenstein, dass das Spiel Go in die Komplexitäts-Klasse Pspace fällt.[2] Er beschäftigt sich mit dem P-NP-Problem.[3]

Er ist Mitglied der American Academy of Arts and Sciences.

Zu seinen Doktoranden zählt Lance Fortnow.

Schriften

  • Sipser Introduction to the theory of computation, PWS Publishing, Boston 1996, 2. Auflage Thomson Course Technology, Boston 2006, ISBN 053494728X

Weblinks

Einzelnachweise

  1. Richard Lipton in seinem Blog
  2. Proc.19.Annual Symposium Foundation Computer Science, IEEE 1978
  3. zum Beispiel Clay Public Lecture Beyond Computation, Harvard 2006, Vortrag

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

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

  • Michael Sipser — Michael Fredric Sipser is a professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. He received his Ph.D. in 1980 from the University of California, Berkeley under the direction of Manuel… …   Wikipedia

  • Sipser-Lautemann theorem — In computational complexity theory, the Sipser Lautemann theorem or Sipser Gács Lautemann theorem states that BPP (Bounded error Probablistic Polynomial) time, is contained in the polynomial time hierarchy, and more specifically Sigma;2 cap; Pi;2 …   Wikipedia

  • Diagrama de estados — Saltar a navegación, búsqueda si representamos una substancia en un gráfico su presión de vapor para cada temperatura(marcados en el gráfico como líneas gruesas y continuas) y añadimos la temperatura del cambio de estado (marcados como líneas más …   Wikipedia Español

  • Algorithm characterizations — The word algorithm does not have a generally accepted definition. Researchers are actively working in formalizing this term. This article will present some of the characterizations of the notion of algorithm in more detail. This article is a… …   Wikipedia

  • Interactive proof system — In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to… …   Wikipedia

  • IP (complexity) — In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Goldwasser, et al. in 1985. An interactive proof system consists …   Wikipedia

  • Daniel Spielman — Naissance mars 1970 Domicile États Unis Nationalité …   Wikipédia en Français

  • Chomsky normal form — In computer science, a context free grammar is said to be in Chomsky normal form if all of its production rules are of the form: or or where A, B and C are nonterminal symbols, α is a terminal symbol (a symbol that represents a constant value), S …   Wikipedia

  • Post correspondence problem — The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946.[1] Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability. Contents 1… …   Wikipedia

  • Manuel Blum — Born April 26, 1938 (1938 04 26) (age 73) Caracas, Venezuela Residence Pittsburgh …   Wikipedia

Share the article and excerpts

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