|
Carsten Lund
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. 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 systems; 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 pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Aarhus
Aarhus (, , ; officially spelled Århus from 1948 until 1 January 2011) is the second-largest city in Denmark and the seat of Aarhus Municipality. It is located on the eastern shore of Jutland in the Kattegat sea and approximately northwest of Copenhagen. The largest city in Jutland, Aarhus anchors the Central Denmark Region and the statistical region ' (''LØ'') (lit.: Province East Jutland). The LØ is the second most populous statistical region in Denmark with an estimated population of 903,974 (). Aarhus Municipality defines the greater Aarhus area as itself and eight adjacent municipalities totalling 952,824 inhabitants () which is roughly analogous to the municipal and commercial collaboration Business Region Aarhus. The city proper, with an estimated population of 285,273 inhabitants (), ranks as the 2nd-largest city in Denmark. Aarhus dates back to at least the late 8th century and is among the oldest cities in Denmark. It was founded as a harbour settlement at ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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^) Alternatively, NEXPTIME can be defined using deterministic Turing machines as verifiers. A language ''L'' is in NEXPTIME if and only if there exist polynomials ''p'' and ''q'', and a deterministic Turing machine ''M'', such that * For all ''x'' and ''y'', the machine ''M'' runs in time 2^ on input * For all ''x'' in ''L'', there exists a string ''y'' of length 2^ such that * For all ''x'' not in ''L'' and all strings ''y'' of length 2^, We know : and also, by the time hierarchy theorem, that : If , then ( padding argument); more precisely, if and only if there exist sparse languages in NP that are not in P. Alternative characterizations NEXPTIME often arises in the context of interactive proof systems, where there are two maj ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
1963 Births
Events January * January 1 – Bogle–Chandler case: Commonwealth Scientific and Industrial Research Organisation scientist Dr. Gilbert Bogle and Mrs. Margaret Chandler are found dead (presumed poisoned), in bushland near the Lane Cove River, Sydney, Australia. * January 2 – Vietnam War – Battle of Ap Bac: The Viet Cong win their first major victory. * January 9 – A January 1963 lunar eclipse, total penumbral lunar eclipse is visible in the Americas, Europe, Africa, and Asia, and is the 56th lunar eclipse of Lunar Saros 114. Gamma has a value of −1.01282. It occurs on the night between Wednesday, January 9 and Thursday, January 10, 1963. * January 13 – 1963 Togolese coup d'état: A military coup in Togo results in the installation of coup leader Emmanuel Bodjollé as president. * January 17 – A last quarter moon occurs between the January 1963 lunar eclipse, penumbral lunar eclipse and the Solar eclipse of January 25, 1963, annular solar ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Internet Traffic Engineering
Internet traffic engineering is defined as that aspect of Internet network engineering dealing with the issue of performance evaluation and performance optimization of operational IP networks. Traffic engineering encompasses the application of technology and scientific principles to the measurement, characterization, modeling, and control of Internet traffic FC-2702, AWD2 Enhancing the performance of an operational network, at both traffic and resource levels, are major objectives of Internet engineering. This is accomplished by addressing traffic performance requirements, while utilizing network economically and reliably. Traffic oriented performance includes packet transfer delay, packet delay variation, packet loss, and throughput. An important objective of Internet traffic engineering is to facilitate reliable network operations FC-2702 This can be done by providing mechanisms that network integrity and by embracing policies emphasizing survivability. This results in a minimi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
SIGACT
ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer. Publications SIGACT publishes a quarterly print newsletter, ''SIGACT News''. Its online version, ''SIGACT News Online'', is available since 1996 for SIGACT members, with unrestricted access to some features. Conferences SIGACT sponsors or has sponsored several annual conferences. *COLT: Conference on Learning Theory, until 1999 *PODC: ACM Symposium on Principles of Distributed Computing (jointly sponsored by SIGOPS) *PODS: ACM Symposium on Principles of Database Systems *POPL: ACM Symposium on Principles of Programming Languages *SOCG: ACM Symposium on Computational Geometry (jointly sponsored by SIGGRAPH), until 2014 *SODA: ACM/SIAM Symposium on Discrete Algorithms (jointly sponsored by the Society for Industrial and Applied Mathematics) ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Approximation Ratio
An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ''ad-'' (''ad-'' before ''p'' becomes ap- by assimilation) meaning ''to''. Words like ''approximate'', ''approximately'' and ''approximation'' are used especially in technical or scientific contexts. In everyday English, words such as ''roughly'' or ''around'' are used with a similar meaning. It is often found abbreviated as ''approx.'' The term can be applied to various properties (e.g., value, quantity, image, description) that are nearly, but not exactly correct; similar, but not exactly the same (e.g., the approximate time was 10 o'clock). Although approximation is most often applied to numbers, it is also frequently applied to such things as mathematical functions, shapes, and physical laws. In science, approximation can refer to us ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. Scope Hardness of approximation complements the study of approximation algorithms by proving, for certain problems, a limit on the factors with which their solution can be efficiently approximated. Typically such limits show a factor of approximation beyond which a problem becomes NP-hard, implying that finding a polynomial time approximation for the problem is impossible unless NP=P. Some hardness of approximation results, however, are based on other hypotheses, a notable one among which is the unique games conjecture. History Since the early 1970s it was known that many optimization problems could not be solved in polynomial time unless P = NP, but in many of these problems the optimal solution could be efficiently approximated to a certain degree. In the 1970s, Teofilo F. Gonzalez and Sartaj Sahni began the study of hard ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem. A more precise specification is: a problem ''H'' is NP-hard when every problem ''L'' in NP can be reduced in polynomial time to ''H''; that is, assuming a solution for ''H'' takes 1 unit time, ''H''s solution can be used to solve ''L'' in polynomial time. As a consequence, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. As it is suspected that P≠NP, it is unlikely that such an algorithm exists. It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven. Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class. Def ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof (or certificate), as used in the verifier-based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way. Probabilistically checkable proofs give rise to many complexity classes depending on the number of queries required and the amount of randomness used. The class PCP 'r''(''n''),''q''(''n'')re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. He held a Lady Davis Postdoctoral Fellowship at the Hebrew University, Jerusalem (1989–90), a postdoc at the University of Chicago, 1991–92, and a postdoc at Bell Laboratories (1992). Szegedy's research areas include computational complexity theory and quantum computing Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though .... He was awarded the Gödel Prize twice, in 2001 and 2005, for his work on probabilistically checkable proofs and on the space complexity of approximating the frequency moments in streamed data. His work on streaming was also recognized b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rajeev Motwani
Rajeev Motwani (Hindi: राजीव मोटवानी , March 24, 1962 – June 5, 2009) was an Indian American 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 2001. Education Rajeev Motwani was born in Jammu, Jammu and Kashmir, India on March 24, 1962, into a Sindhi Hindu family and grew up in New Delhi. His father was in the Indian Army. He had two brothers. As a child, inspired by luminaries like Gauss, he wanted to become a mathematician. Motwani went to St Columba's School, New Delhi. He completed his B.Tech. in Computer Science from the Indian Institute of Technology Kanpur in Kanpur, Uttar Pradesh in 1983 and got his Ph.D. in Computer Science from the University of California, Berkeley in Berkeley, California, United States in 1988, under the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 his bachelor's degree in computer science from IIT Delhi in 1987 and his doctoral degree in computer science at the University of California, Berkeley in 1992. He was a research staff member at the IBM Thomas J. Watson Research Center in Yorktown Heights, New York from 1992 to 1997 and moved to MIT after that. From 2009 to 2015 he was a permanent researcher at Microsoft Research New England before joining Harvard University in 2015. Research contribution and awards He was awarded the Rolf Nevanlinna Prize at the 24th International Congress of Mathematicians (ICM) in 2002. The prize recognizes outstanding work in the mathematical aspects of computer science. Sudan was honored for his work in advancing the theory of probabilisticall ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
