Carsten Lund
Encyclopedia
Carsten Lund is a Danish
-born theoretical computer scientist
, currently working at AT&T Labs
in Florham Park, New Jersey
, United States.
Lund was born in Aarhus
, Denmark
, and received the
“kandidat” degree in 1988 from the University of Aarhus
and his Ph.D.
from the University of Chicago
in computer science. His thesis, entitled The
Power of Interaction, was chosen as an ACM
'Distinguished Dissertation'.
Lund was a co-author on two of five competing papers at the 1990 Symposium on Foundations of Computer Science
characterizing complexity classes
such as PSPACE
and NEXPTIME
in terms of interactive proof system
s;
this work became part of his 1991 Ph.D. thesis from the University of Chicago
under the supervision of Lance Fortnow
and László Babai
, for which he was a runner-up for the 1991 ACM
Doctoral Dissertation Award.
He is also known for his joint work with Sanjeev Arora
, Madhu Sudan
, Rajeev Motwani
, and Mario Szegedy
that discovered the existence of probabilistically checkable proofs for NP-hard
problems and used them to prove hardness results
for approximation problems; in 2001 he and his co-authors received the Gödel Prize
for their share in these discoveries.
More recently he has published highly-cited work on internet traffic engineering
.
He has been working for AT&T Laboratories since August 1991.
Denmark
Denmark is a Scandinavian country in Northern Europe. The countries of Denmark and Greenland, as well as the Faroe Islands, constitute the Kingdom of Denmark . It is the southernmost of the Nordic countries, southwest of Sweden and south of Norway, and bordered to the south by Germany. Denmark...
-born theoretical computer scientist
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, currently working at AT&T Labs
AT&T Labs
AT&T Labs, Inc. is the research & development division of AT&T, where scientists and engineers work to understand and advance innovative technologies relevant to networking, communications, and information. Over 1800 employees work in six locations: Florham Park, NJ; Middletown, NJ; Austin, TX;...
in Florham Park, New Jersey
Florham Park, New Jersey
Florham Park is a borough in Morris County, New Jersey, United States. As of the United States 2000 Census, the borough population was 8,857, which had grown to 12,389 as of the Bureau's 2008 estimate....
, United States.
Lund was born in Aarhus
Aarhus
Aarhus or Århus is the second-largest city in Denmark. The principal port of Denmark, Aarhus is on the east side of the peninsula of Jutland in the geographical center of Denmark...
, Denmark
Denmark
Denmark is a Scandinavian country in Northern Europe. The countries of Denmark and Greenland, as well as the Faroe Islands, constitute the Kingdom of Denmark . It is the southernmost of the Nordic countries, southwest of Sweden and south of Norway, and bordered to the south by Germany. Denmark...
, and received the
“kandidat” degree in 1988 from the University of Aarhus
University of Aarhus
Aarhus University , located in the city of Aarhus, Denmark, is Denmark's second oldest and second largest university...
and his Ph.D.
from the University of Chicago
University of Chicago
The University of Chicago is a private research university in Chicago, Illinois, USA. It was founded by the American Baptist Education Society with a donation from oil magnate and philanthropist John D. Rockefeller and incorporated in 1890...
in computer science. His thesis, entitled The
Power of Interaction, was chosen as an ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
'Distinguished Dissertation'.
Lund was a co-author on two of five competing papers at the 1990 Symposium on Foundations of Computer Science
Symposium on Foundations of Computer Science
FOCS, the Annual IEEE Symposium on Foundations of Computer Science, is an academic conference in the field of theoretical computer science...
characterizing complexity classes
Computational complexity theory
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...
such as PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
and NEXPTIME
NEXPTIME
In computational complexity theory, the complexity class NEXPTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O for some polynomial p, and unlimited space....
in terms of interactive proof system
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 ascertain whether a given string belongs to a...
s;
this work became part of his 1991 Ph.D. thesis from the University of Chicago
University of Chicago
The University of Chicago is a private research university in Chicago, Illinois, USA. It was founded by the American Baptist Education Society with a donation from oil magnate and philanthropist John D. Rockefeller and incorporated in 1890...
under the supervision of Lance Fortnow
Lance Fortnow
Lance Jeremy Fortnow is a computer scientist in the field of computational complexity and its applications, notable for producing major results on interactive proof systems.-Biography:...
and László Babai
László Babai
László Babai is a Hungarian professor of mathematics and computer science at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields...
, for which he was a runner-up for the 1991 ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
Doctoral Dissertation Award.
He is also known for his joint work with Sanjeev Arora
Sanjeev Arora
Sanjeev Arora is a theoretical computer scientist who is best known for his work on probabilistically checkable proofs and, in particular, the PCP theorem. He is currently the Charles C...
, Madhu Sudan
Madhu Sudan
Madhu Sudan is an Indian computer scientist, professor of computer science at the Massachusetts Institute of Technology and a member of MIT Computer Science and Artificial Intelligence Laboratory.-Career:...
, Rajeev Motwani
Rajeev Motwani
Rajeev Motwani was a professor of Computer Science at Stanford University whose research focused on theoretical computer science. He was an early advisor and supporter of companies including Google and PayPal, and a special advisor to Sequoia Capital. He was a winner of the Gödel Prize in...
, and Mario Szegedy
Mario Szegedy
Mario Szegedy is a Hungarian computer scientist, professor of computer science at Rutgers University. He received his Ph.D. in computer science in 1989 from the University of Chicago...
that discovered the existence of probabilistically checkable proofs for NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
problems and used them to prove hardness results
Hardness of approximation
In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. It complements the study of approximation algorithms by proving, for certain problems, a limit on the factors with which their solution can...
for approximation problems; in 2001 he and his co-authors received the Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
for their share in these discoveries.
More recently he has published highly-cited work on internet traffic engineering
Internet traffic engineering
Internet traffic engineering refers to all the work related to the physical network that carries Internet traffic between different networks with the objective of reaching the highest levels of capacity in the Internet backbone.-References:Abdel-Hameed Nawar, "E-Commerce" Lecture Notes, Cairo...
.
He has been working for AT&T Laboratories since August 1991.