Carsten Lund (born July 1, 1963) is a Danish-born

theoretical computer scientist Theoretical computer science is a subfield of computer science and mathematics that focuses on the abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The ACM's Special Inter ...

, currently working at

AT&T Labs AT&T Labs, Inc. (formerly AT&T Laboratories, Inc.) is the research & development division of AT&T, the telecommunications company. It employs some 1,800 people in various locations, including: Bedminster, New Jersey; Middletown Township, New J ...

Bedminster, New Jersey Bedminster is a Township (New Jersey), township in Somerset County, New Jersey, Somerset County, in the U.S. state of New Jersey. As of the 2020 United States census, the township's population was 8,272, an increase of 107 (+1.3%) from the 201 ...

, United States. Lund was born in

Aarhus Aarhus (, , ; officially spelled Århus from 1948 until 1 January 2011) is the second-largest city in Denmark and the seat of Aarhus municipality, Aarhus Municipality. It is located on the eastern shore of Jutland in the Kattegat sea and app ...

Denmark Denmark is a Nordic countries, Nordic country in Northern Europe. It is the metropole and most populous constituent of the Kingdom of Denmark,, . also known as the Danish Realm, a constitutionally unitary state that includes the Autonomous a ...

, and received the "kandidat" degree in 1988 from the

University of Aarhus Aarhus University (, abbreviated AU) is a public research university. Its main campus is located in Aarhus, Denmark. It is the second largest and second oldest university in Denmark. The university is part of the Coimbra Group, the Guild, and Utr ...

and his Ph.D. from the

University of Chicago The University of Chicago (UChicago, Chicago, or UChi) is a Private university, private research university in Chicago, Illinois, United States. Its main campus is in the Hyde Park, Chicago, Hyde Park neighborhood on Chicago's South Side, Chic ...

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 The IEEE Annual Symposium on Foundations of Computer Science (FOCS) is an academic conference in the field of theoretical computer science. FOCS is sponsored by the IEEE Computer Society. As writes, FOCS and its annual Association for Computing ...

characterizing

complexity classes In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...

such as

PSPACE In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''f''(''n'')), the set of all problems that can ...

and

NEXPTIME In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2^. In terms of NTIME, :\mathsf = \bigcup_ \mathsf(2^) ...

in terms of

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: a ''prover'' and a ''verifier''. The parties interact by exchanging messages in order ...

s; this work became part of his 1991 Ph.D. thesis from the

under the supervision of

Lance Fortnow Lance Jeremy Fortnow (born August 15, 1963) is a computer scientist known for major results in Computational complexity theory, computational complexity and interactive proof systems. Since 2019, he has been at the Illinois Institute of Technology ...

and

László Babai László "Laci" Babai (born July 20, 1950, in Budapest) a fellow of the American Academy of Arts and Sciences, and won the Knuth Prize. Babai was an invited speaker at the International Congresses of Mathematicians in Kyoto (1990), Zürich (199 ...

, 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 Sanjeev Arora (born January 1968) is an Indian-American theoretical computer scientist who works in AI and Machine learning. Life Sanjeev scored the IIT JEE number 1 rank in 1986 He was a visiting scholar at the Institute for Advanced Study in ...

Madhu Sudan Madhu Sudan (born 12 September 1966) is an Indian-American computer scientist. He has been a Gordon McKay Professor of Computer Science at the Harvard John A. Paulson School of Engineering and Applied Sciences since 2015. Career He received hi ...

Rajeev Motwani Rajeev Motwani (Hindi: राजीव मोटवानी , 24 March 1962 – 5 June 2009) was an Indian-American professor of computer science at Stanford University whose research focused on theoretical computer science. He was a special a ...

, and

Mario Szegedy Mario Szegedy (born October 23, 1960) is a Hungarian-American computer scientist, professor of computer science at Rutgers University. He received his Ph.D. in computer science in 1989 from the University of Chicago after completing his disserta ...

that discovered the existence of

probabilistically checkable proof In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is ...

s for

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

problems and used them to prove hardness results for approximation problems; in 2001 he and his co-authors received the

Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...

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.

References

External links

AT&T Labs Homepage
{{DEFAULTSORT:Lund, Carsten 1963 births Living people Theoretical computer scientists Scientists at Bell Labs Aarhus University alumni People from New Jersey Gödel Prize laureates Danish computer scientists