Abstract
The Internet has arguably superseded the computer as the most complex cohesive artifact (if you can call it that), and is, quite predictably, the source of a new generation of foundational problems for Theoretical Computer Science. These new theoretical challenges emanate from several novel aspects of the Internet: (a) Its unprecedented size, diversity, and availability as an information repository; (b) its novel nature as a computer system that intertwines a multitude of economic interests in varying degrees of competition; and (c) its history as a shared resource architecture that emerged in a remarkably ad hoc yet gloriously successful manner. In this talk I will survey some recent research (done in collaboration with Joan Feigenbaum, Dick Karp, Elias Koutsoupias, and Scott Shenker, see [1,2]) on problems of the two latter kinds. See [3,5] for examples of theoretical work along the first axis.
Research partially supported by the National Science Foundation
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker, “Sharing the Cost of Multicast Transmissions,” Proc. 2000 STOC.
Richard M. Karp, Elias Koutsoupias, Christos H. Papadimitriou, Scott Shenker, “Optimization Problems in Congestion Control,” manuscript, April 2000.
Jon Kleinberg, “Authoritative sources in a hyperlinked environment,” Proc. ACM-SIAM Symposium on Discrete Algorithms, 1998.
Van Jacobson “Congestion Avoidance and Control,” in ACM SigComm Proceedings, pp 314–329, 1988.
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala, “Latent Semantic Indexing: A Probabilistic Analysis,” Proc. 1998 PODS, to appear in the special issue of JCSS.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Papadimitriou, C.H. (2000). Theoretical Problems Related to the Internet. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_1
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive