Tim Roughgarden

Last updated

Timothy Avelin Roughgarden
Tim Roughgarden 2022.jpg
Roughgarden in 2022
Born (1975-07-20) July 20, 1975 (age 48)
Alma mater
Known forContributions to Selfish Routing in the context of Computer Science
Awards
Scientific career
Fields Computer Science, Game Theory
Institutions
Thesis Selfish routing  (2002)
Doctoral advisor Éva Tardos
Website http://timroughgarden.org/

Timothy Avelin Roughgarden (born July 20, 1975) is an American computer scientist and a professor of Computer Science at Columbia University. [1] Roughgarden's work deals primarily with game theoretic questions in computer science.

Contents

Roughgarden received his Ph.D. from Cornell University in 2002, under the supervision of Éva Tardos. [2] He did a postdoc at University of California, Berkeley in 2004. From 2004 to 2018, Roughgarden was a professor at the Computer Science department at Stanford University working on algorithms and game theory. Roughgarden teaches a four-part algorithms specialization on Coursera. [3]

He received the Danny Lewin award at STOC 2002 for the best student paper. He received the Presidential Early Career Award for Scientists and Engineers in 2007, [4] the Grace Murray Hopper Award in 2009, [5] and the Gödel Prize in 2012 for his work on routing traffic in large-scale communication networks to optimize performance of a congested network. [6] [7] He received a Guggenheim Fellowship in 2017 [8] [9] and the Kalai Prize in 2016.

Roughgarden is a co-editor of the 2016 textbook Algorithmic Game Theory, as well as the author of two chapters (Introduction to the Inefficiency of Equilibria and Routing Games). [10] [11]

Selected publications

Related Research Articles

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.

<span class="mw-page-title-main">Daphne Koller</span> Israeli-American computer scientist

Daphne Koller is an Israeli-American computer scientist. She was a professor in the department of computer science at Stanford University and a MacArthur Foundation fellowship recipient. She is one of the founders of Coursera, an online education platform. Her general research area is artificial intelligence and its applications in the biomedical sciences. Koller was featured in a 2004 article by MIT Technology Review titled "10 Emerging Technologies That Will Change Your World" concerning the topic of Bayesian machine learning.

<span class="mw-page-title-main">Éva Tardos</span> Hungarian mathematician

Éva Tardos is a Hungarian mathematician and the Jacob Gould Schurman Professor of Computer Science at Cornell University.

<span class="mw-page-title-main">Christos Papadimitriou</span> Greek computer scientist (b. 1949)

Christos Charilaos Papadimitriou is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.

<span class="mw-page-title-main">Knuth Prize</span> Prize given by ACM and IEEE for outstanding contributions to the foundations of computer science

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.

<span class="mw-page-title-main">Dan Boneh</span> Israeli–American professor

Dan Boneh is an Israeli–American professor in applied cryptography and computer security at Stanford University.

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."

Manfred Klaus Warmuth is a computer scientist known for his pioneering research in computational learning theory. He is a Distinguished Professor emeritus at the University of California, Santa Cruz.

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.

<span class="mw-page-title-main">Rajeev Motwani</span> Indian computer scientist (1962–2009)

Rajeev Motwani was an Indian American professor of Computer Science at Stanford University whose research focused on theoretical computer science. He was a special advisor to Sequoia Capital. He was a winner of the Gödel Prize in 2001.

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.

The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computing Machinery special interest group SIGACT. Acceptance rate of STOC, averaged from 1970 to 2012, is 31%, with the rate of 29% in 2012.

<span class="mw-page-title-main">Gábor Tardos</span> Hungarian mathematician

Gábor Tardos is a Hungarian mathematician, currently a professor at Central European University and previously a Canada Research Chair at Simon Fraser University. He works mainly in combinatorics and computer science. He is the younger brother of Éva Tardos.

<span class="mw-page-title-main">Joseph S. B. Mitchell</span> American computer scientist and mathematician

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.

<span class="mw-page-title-main">Noam Nisan</span> Israeli computer scientist

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.

Michael Justin Kearns is an American computer scientist, professor and National Center Chair at the University of Pennsylvania, the founding director of Penn's Singh Program in Networked & Social Systems Engineering (NETS), the founding director of Warren Center for Network and Data Sciences, and also holds secondary appointments in Penn's Wharton School and department of Economics. He is a leading researcher in computational learning theory and algorithmic game theory, and interested in machine learning, artificial intelligence, computational finance, algorithmic trading, computational social science and social networks. He previously led the Advisory and Research function in Morgan Stanley's Artificial Intelligence Center of Excellence team, and is currently an Amazon Scholar within Amazon Web Services.

The Prize in Game Theory and Computer Science in Honour of Ehud Kalai is an award given by the Game Theory Society. The prize is awarded for outstanding articles at the interface of game theory and computer science. Following the eligibility rules of the Gödel Prize, preference is given to authors who are 45 years old or younger at the time of the award. It was established in 2008 by a donation from Yoav Shoham in honor of the Ehud Kalai's contributions in bridging these two fields.

Amir Ronen is an Israeli computer scientist.

References

  1. "Tim Roughgarden's Homepage". theory.stanford.edu. Retrieved July 6, 2015.
  2. "Tim Roughgarden's Profile - Stanford Profiles". soe.stanford.edu. Stanford University. Archived from the original on July 17, 2012. Retrieved July 6, 2015.
  3. "Algorithms Specialization". coursera.org. Coursera Inc. Retrieved May 17, 2017.
  4. "White House Announces 2007 Awards for Early Career Scientists and Engineers". The George W. Bush White House Archives (Press release). Washington, D.C.: Office of Science and Technology Policy. December 19, 2008. Retrieved January 19, 2020.
  5. "ACM Awards Recognize Computer Science Innovation". acm.org (Press release). Association for Computing Machinery. March 31, 2010. Retrieved January 19, 2020.
  6. "The Gödel Prize 2012 - Laudatio". European Association for Theoretical Computer Science. 2012. Retrieved January 19, 2020.
  7. "ACM Gödel Prize for Seminal Papers in Algorithmic Game Theory". Game Theory Society. June 3, 2012. Retrieved January 19, 2020.
  8. "Tim Roughgarden: Fellow, Awarded 2017". gf.org. John Simon Guggenheim Memorial Foundation. 2017. Retrieved January 19, 2020.
  9. Knowles, Hannah (April 17, 2017). "Four professors named Guggenheim fellows". The Stanford Daily . Retrieved January 19, 2020.
  10. Hrsg., Nisan, Noam (September 24, 2007). Algorithmic game theory. Cambridge University Press. ISBN   978-0-521-87282-9. OCLC   870638977.{{cite book}}: CS1 maint: multiple names: authors list (link)
  11. "Tim Roughgarden's Books and Surveys". timroughgarden.org. Retrieved April 7, 2021.