Related Research Articles
Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.
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 Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.
Éva Tardos is a Hungarian mathematician and the Jacob Gould Schurman Professor of Computer Science at Cornell University.
Christos Charilaos Papadimitriou is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.
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.
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth.
Omer Reingold is an Israeli computer scientist. He is the Rajeev Motwani professor of Computer Science in the Computer Science Department at Stanford University and the director of the Simons Collaboration on the Theory of Algorithmic Fairness. He received a PhD in computer science at Weizmann in 1998 under Moni Naor. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for st-connectivity in undirected graphs. He, along with Avi Wigderson and Salil Vadhan, won the Gödel Prize (2009) for their work on the zig-zag product. He became a Fellow of the Association for Computing Machinery in 2014 "For contributions to the study of pseudorandomness, derandomization, and cryptography."
Algorithmic mechanism design (AMD) lies at the intersection of economic game theory, optimization, and computer science. The prototypical problem in mechanism design is to design a system for multiple self-interested participants, such that the participants' self-interested actions at equilibrium lead to good system performance. Typical objectives studied include revenue maximization and social welfare maximization. Algorithmic mechanism design differs from classical economic mechanism design in several respects. It typically employs the analytic tools of theoretical computer science, such as worst case analysis and approximation ratios, in contrast to classical mechanism design in economics which often makes distributional assumptions about the agents. It also considers computational constraints to be of central importance: mechanisms that cannot be efficiently implemented in polynomial time are not considered to be viable solutions to a mechanism design problem. This often, for example, rules out the classic economic mechanism, the Vickrey–Clarke–Groves auction.
Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments.
Shang-Hua Teng is a Chinese-American computer scientist. He is the Seeley G. Mudd Professor of Computer Science and Mathematics at the University of Southern California. Previously, he was the chairman of the Computer Science Department at the Viterbi School of Engineering of the University of Southern California.
Nir Shavit is an Israeli computer scientist. He is a professor in the Computer Science Department at Tel Aviv University and a professor of electrical engineering and computer science at the Massachusetts Institute of Technology.
Lance Jeremy Fortnow is a computer scientist known for major results in computational complexity and interactive proof systems. As of January 2024, he was the Dean of the College of Computing at the Illinois Institute of Technology.
Constantinos Daskalakis is a Greek theoretical computer scientist. He is a professor at MIT's Electrical Engineering and Computer Science department and a member of the MIT Computer Science and Artificial Intelligence Laboratory. He was awarded the Rolf Nevanlinna Prize and the Grace Murray Hopper Award in 2018.
Joseph S. B. Mitchell is an American computer scientist and mathematician. He is Distinguished Professor and Department Chair of Applied Mathematics and Statistics and Research Professor of Computer Science at Stony Brook University.
Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.
Timothy Avelin Roughgarden is an American computer scientist and a professor of Computer Science at Columbia University. Roughgarden's work deals primarily with game theoretic questions in computer science.
Andrew Vladislav Goldberg is an American computer scientist working primarily on design, analysis, and experimental evaluation of algorithms. He also worked on mechanism design, computer systems, and complexity theory. Currently he is a Senior Principal Scientist at Amazon.com.
Truthful job scheduling is a mechanism design variant of the job shop scheduling problem from operations research.
A knapsack auction is an auction in which several identical items are sold, and there are several bidders with different valuations interested in different amounts of items. The goal is to choose a subset of the bidders with a total demand, at most, the number of items and, subject to that, a maximum total value. Finding this set of bidders requires solving an instance of the knapsack problem, which explains the term "knapsack auction".
References
- ↑ "ACM SIGACT Presents Gödel Prize for Research that Illuminated Effects of Selfish Internet Use — Association for Computing Machinery". acm.org. 2012-07-12. Retrieved 2024-01-15.
- ↑ Nisan, Noam; Ronen, Amir (1999-05-01). "Algorithmic mechanism design (extended abstract)". Proceedings of the thirty-first annual ACM symposium on Theory of Computing. STOC '99. New York, NY, USA: Association for Computing Machinery: 129–140. doi:10.1145/301250.301287. ISBN 978-1-58113-067-6.
- ↑ Nisan, Noam; Ronen, Amir (2001-04-01). "Algorithmic Mechanism Design". Games and Economic Behavior. 35 (1): 166–196. doi:10.1006/game.1999.0790. ISSN 0899-8256.