Carsten Lund (born July 1, 1963) is a Danish-born theoretical computer scientist, currently working at AT&T Labs in Bedminster, New Jersey, United States.
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 systems;[2][3][4] 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,[5] for which he was a runner-up for the 1991 ACM Doctoral Dissertation Award.
[6] 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;[7][8] in 2001 he and his co-authors received the Gödel Prize for their share in these discoveries.
[9] More recently he has published highly cited work on internet traffic engineering.