Lance Fortnow

Lance Fortnow

Lance Jeremy Fortnow ist ein amerikanischer Informatiker.

Fortnow studierte Mathematik und Informatik an der Cornell University (Bachelor 1985) und wurde 1989 bei Michael Sipser am Massachusetts Institute of Technology promoviert (Complexity theoretic aspects of interactive proof systems). 1989 wurde er Assistant Professor, 1994 Associate Professor und 2003 Professor für Informatik an der University of Chicago. Seit 2008 ist er Professor an der Northwestern University und Adjunct Professor am Toyota Technology Institute at Chicago und außerdem seit 2008 am Kellogg Graduate Institute of Management Science. 1996/97 war er als Fulbright-Stipendiat Gastprofessor am Centrum Wiskunde & Informatica in Amsterdam und 1999 bis 2003 Senior Scientist am NEC Research Institute in Princeton. 2001/2002 war er Gastprofessor an der Princeton University.

Zu seinen Doktoranden zählt Carsten Lund, und mit diesem und László Babai erzielte er Anfang der 1990er Jahre wichtige Fortschritte in der Komplexitätstheorie von zufallsgesteuerten Beweissystemen (Probabilistic Checkable Proofs, PCP) bzw. interaktiven Beweissystemen. Insbesondere bewiesen sie, dass die Klasse der Beweise von nicht-deterministischen Turingmaschinen mit exponentiellem Zeitaufwand in der Klasse PCP (mit polynomialer Komplexität der Fragen und der verwendeten Zufallszahlen) ist (NEXPPCP[poly(n), poly(n)]). Die Bemühungen, die Klasse zu erweitern führten dann in den 1990er Jahren zum PCP-Theorem.

Seit den 2000er Jahren beschäftigt er sich auch mit Anwendungen der Komplexitätstheorie in den Wirtschaftswissenschaften, wo er unter anderem das Gefangenendilemma mit Duke Whang spieltheoretisch untersuchte und logarithmische Prognoseregeln für Märkte (Market Scoring Rules) von Robin Hanson.

Seit 2007 ist er Fellow der Association for Computing Machinery. Er ist Mitgründer und Herausgeber der ACM Transactions on Computation Theory.

Schriften

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

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

  • Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia

  • P versus NP problem — Unsolved problems in computer science Is P = NP ? …   Wikipedia

  • Problème P = NP — En mathématiques, et plus précisément en informatique théorique, la relation entre la classe des problèmes de complexité P et la classe des problèmes de complexité NP est un problème non résolu, et est considéré par de nombreux chercheurs comme… …   Wikipédia en Français

  • Sparse language — In computational complexity theory, a sparse language is a formal language (a set of strings) such that the number of strings of length n in the language is bounded by a polynomial function of n . They are used primarily in the study of the… …   Wikipedia

  • Quantum Turing machine — A Quantum Turing machine (QTM) is an abstract machine used to model the effect of a quantum computer. It provides a very simple model which captures all of the power of quantum computation. Any quantum algorithm can be expressed formally as a… …   Wikipedia

  • Computers and Intractability: A Guide to the Theory of NP-Completeness — Computers and Intractability: A Guide to the Theory of NP Completeness …   Wikipedia

  • PCP-Theorem — Das PCP Theorem ist ein Satz aus der theoretischen Informatik (Komplexitätstheorie). Es beruht auf dem Konzept des zufällig verifizierbaren Beweises eines mathematischen Satzes (probabilistic checkable proof, PCP), der wiederum auf das Konzept… …   Deutsch Wikipedia

  • BPP — In complexity theory, BPP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most 1/3 for all instances. The abbreviation BPP refers to Bounded error, Probabilistic,… …   Wikipedia

  • Integer factorization — In number theory, integer factorization is the way of breaking down a composite number into smaller non trivial divisors, which when multiplied together equal the original integer.When the numbers are very large, no efficient integer… …   Wikipedia

  • Recursion theory — Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability… …   Wikipedia

Share the article and excerpts

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