February 25, 2010, at 05:41 PM
by David Zuckerman
Changed lines 39-41 from:
to:
- Can Random Coin Flips Speed Up a Computer? by David Zuckerman. An introduction to randomness and computation targeting a general audience.
August 14, 2009, at 03:47 AM
by Oded Goldreich
Changed lines 37-44 from:
- Theory of Computation: A Scientific Perspective by Oded Goldreich and Avi Wigderson \\
This essay provides an assessment of the Theory of Computing (TOC)
as a fundamental scientific discipline.
The focus is on the important scientific role of TOC,
and on its great achievements, productivity and impact
(both scientific and technological) so far.
to:
- Theory of Computation: A Scientific Perspective by Oded Goldreich and Avi Wigderson - provides an assessment of the Theory of Computing (TOC) as a fundamental scientific discipline. The focus is on the important scientific role of TOC, and on its great achievements, productivity and impact (both scientific and technological) so far. Also includes brief layman-level introductions to four concrete topics.
August 14, 2009, at 03:38 AM
by Oded Goldreich
Changed lines 37-38 from:
- Theory of Computation: A Scientific Perspective by Oded Goldreich and Avi Wigderson
to:
- Theory of Computation: A Scientific Perspective by Oded Goldreich and Avi Wigderson \\
This essay provides an assessment of the Theory of Computing (TOC)
as a fundamental scientific discipline.
The focus is on the important scientific role of TOC,
and on its great achievements, productivity and impact
(both scientific and technological) so far.
August 13, 2009, at 08:58 AM
by 132.77.4.129
Added lines 37-38:
- Theory of Computation: A Scientific Perspective by Oded Goldreich and Avi Wigderson
August 05, 2009, at 07:52 AM
by Oded Goldreich
Changed lines 53-56 from:
Following a general introduction to the two notions and their possible relation,
the essey contains brief accounts of pseudorandomness and probabilistic proof systems
and every shorter accounts of cryptography and sub-linear time algorithms.
to:
Following a general introduction to the two notions and their possible relation, the essey contains brief accounts of pseudorandomness and probabilistic proof systems and every shorter accounts of cryptography and sub-linear time algorithms.
August 05, 2009, at 07:50 AM
by Oded Goldreich
Changed lines 52-53 from:
- Randomness and Computation by Oded Goldreich
to:
- Randomness and Computation by Oded Goldreich
Following a general introduction to the two notions and their possible relation,
the essey contains brief accounts of pseudorandomness and probabilistic proof systems
and every shorter accounts of cryptography and sub-linear time algorithms.
August 05, 2009, at 07:42 AM
by Oded Goldreich
Added lines 52-53:
- Randomness and Computation by Oded Goldreich
April 22, 2009, at 03:22 PM
by John A
Changed lines 67-68 from:
- In Theory - Luca Trevisan
to:
- In Theory - Luca Trevisan
- 0xDE - David Eppstein
- Algorithmic Game Theory - Noam Nisan
- Gödel’s Lost Letter and P=NP - Richard Lipton
March 10, 2008, at 02:54 PM
by Salil Vadhan
Added lines 40-41:
- Beyond Computation Video of Clay Public Lecture by Michael Sipser on the P vs. NP question.
March 03, 2008, at 06:05 PM
by Salil Vadhan
Changed lines 6-7 from:
Click the edit button to add more references to this page.
to:
Click here for instructions on how to make edits, including the password.
February 29, 2008, at 05:17 PM
by Salil Vadhan
Changed lines 79-92 from:
- Alan Turing: The Enigma by Andrew Hodges.
The biography of one of our founding fathers.
Dennis Shasha and Cathy Lazere
Interviews with 15 notable computer scientists, including our own Edsger Dijkstra,
Michael Rabin,
Donald Knuth,
Robert Tarjan,
Leslie Lamport,
Steve Cook,
and
Leonid Levin.
to:
- Alan Turing: The Enigma by Andrew Hodges. The biography of one of our founding fathers.
- Out Of Their Minds byDennis Shasha and Cathy Lazere. Interviews with 15 notable computer scientists, including our own Edsger Dijkstra, Michael Rabin, Donald Knuth, Robert Tarjan, Leslie Lamport, Steve Cook, and Leonid Levin.
February 29, 2008, at 05:13 PM
by Salil Vadhan
Added lines 77-92:
- Turing by Christos Papadimitriou. A novel about computation.
- Alan Turing: The Enigma by Andrew Hodges.
The biography of one of our founding fathers.
Dennis Shasha and Cathy Lazere
Interviews with 15 notable computer scientists, including our own Edsger Dijkstra,
Michael Rabin,
Donald Knuth,
Robert Tarjan,
Leslie Lamport,
Steve Cook,
and
Leonid Levin.
February 28, 2008, at 06:09 PM
by Salil Vadhan
Changed lines 4-5 from:
to:
Added lines 77-83:
Ideas from Other Fields (to inspire us)
- The physicists are the unquestioned masters in exposition and outreach. Here are some inspirations: http://interactions.org/quantumdiaries/ http://www.interactions.org/cms/ http://golem.ph.utexas.edu/string/ Unfortunately, they can also be ruthless in shooting down each other; see http://www.math.columbia.edu/~woit/blog/
- Continuing on this physicists theme, see the American Institute of Physics Success Stories. Note how they take credit for computer related jobs.
- The Clay Mathematics Institute sponsored a series of popular lectures on NP-completeness in 2000. They also provided support for the PCMI/IAS program on Computational Complexity that year. They also do outreach and education concerning pure and applied mathematical topics.
February 28, 2008, at 05:30 PM
by Salil Vadhan
Changed lines 15-16 from:
- The Importance of Mathematics by Tymothy Gowers - talks also about specific theoretical computer science examples, but also the general points apply very strongly to TCS as well.
to:
- The Importance of Mathematics by Timothy Gowers - talks also about specific theoretical computer science examples, but also the general points apply very strongly to TCS as well.
February 28, 2008, at 05:30 PM
by Salil Vadhan
Changed lines 37-39 from:
For CS/Math/Sciences audience
to:
For CS/Math/Science audience
February 28, 2008, at 05:29 PM
by Salil Vadhan
Added lines 3-5:
Added line 8:
Deleted line 16:
Added line 37:
Changed line 50 from:
to:
Changed lines 58-59 from:
to:
Added line 67:
April 06, 2006, at 10:49 AM
by 24.215.197.138
Changed lines 7-8 from:
- description of TCS by Avrim Blum.
to:
- Description of TCS by Avrim Blum.
April 06, 2006, at 10:48 AM
by 24.215.197.138
Changed lines 7-8 from:
to:
- description of TCS by Avrim Blum.
April 06, 2006, at 10:48 AM
by 24.215.197.138
Added lines 7-8:
April 06, 2006, at 10:36 AM
by 162.83.193.25
Changed lines 5-20 from:
Popular books (not aimed at students)
- Computers Ltd: What they really can't do by David Harel. This is a beautiful, well-written and enjoyable book. It presents with meticulous clarity the fundamental results of computability and complexity theory to a non-mathematical audience, and briefly surveys novel models of computation such as quantum computing and molecular computing. Harel also explains how the computational intractability of some problems can be put to good use in fields like public-key cryptography. There should be more books like this one!
- The Advent of the Algorithm: The Idea That Rules The World by David Berlinski. Popular book that covers the emergence of the algorithm as a separate concept, with a historical focus on such figures as Frege and Turing. I personally (-David Molnar) do not care for it, but it is a popular work that treats TCS directly.
(Scott Aaronson: David, I'd go further, and describe this book as a pompous, grandiloquent piece of garbage. It's a clear demonstration of why we need to popularize TCS ourselves: because otherwise the Berlinskis will rush in to fill the void.)
(Maverick Woo: I also agree that better general books should be and could be written. But what has popularization done to the funding situation of the Math community? (They actually do a great job in having general science books in Math.) Did it help? Does it achieve the level of funding that the Math community wants? If TCS do the same, would it be any different?)
- Algorithmics: The Spirit of Computing by David Harel and Yishai Feldman. From the Amazon page: "First published in 1987, explains the basic ideas of algorithms, their structures, and how they manipulate data in computer programs. Of interest to programmers, systems analysts and designers, and software engineers, but the technical level is low enough to be accessible to readers with almost no mathematics or computer background." Makes it sound like a version of _What Is Mathematics?_ for TCS.
- Godel, Escher Bach: An Eternal Golden Braid by Douglas Hofstadter. Belongs at least as much to TCS as it does to AI. This book is the first exposure to TCS ideas for many people.
For high-school students (and younger)
to:
General audience (including high-school students)
- Could Your iPod Be Holding the Greatest Mystery in Modern Science? by Bernard Chazelle
- The Importance of Mathematics by Tymothy Gowers - talks also about specific theoretical computer science examples, but also the general points apply very strongly to TCS as well.
Changed lines 32-33 from:
to:
For CS/Math/Sciences audience
- P, NP and Mathematics by Avi Wigderson
Changed lines 50-53 from:
to:
- Email and the unexpected powers of interaction by Laszlo Babai On the events and the results leading up to interactive proofs for space-bounded computation. (IP=PSPACE).
Changed lines 55-58 from:
- The Computational Complexity Blog - complexity theory
- Ernie's 3D Pancakes - algorithms, geometry
- Vanity of Vanities, all is Vanity - algorithms, geometry
- The Geomblog - algorithms, geometry.
to:
- The Computational Complexity Blog - complexity theory, Lance Fortnow
- Ernie's 3D Pancakes - algorithms, geometry, Jeff Erikson
- Vanity of Vanities, all is Vanity - algorithms, geometry, Sariel Harpeled
- The Geomblog - algorithms, geometry, Suresh Venkatasubramanian
- Shtetl Optimized - Scott Aaronson
- In Theory - Luca Trevisan
Popular books (not aimed at students)
- Computers Ltd: What they really can't do by David Harel. This is a beautiful, well-written and enjoyable book. It presents with meticulous clarity the fundamental results of computability and complexity theory to a non-mathematical audience, and briefly surveys novel models of computation such as quantum computing and molecular computing. Harel also explains how the computational intractability of some problems can be put to good use in fields like public-key cryptography. There should be more books like this one!
- Algorithmics: The Spirit of Computing by David Harel and Yishai Feldman. From the Amazon page: "First published in 1987, explains the basic ideas of algorithms, their structures, and how they manipulate data in computer programs. Of interest to programmers, systems analysts and designers, and software engineers, but the technical level is low enough to be accessible to readers with almost no mathematics or computer background." Makes it sound like a version of _What Is Mathematics?_ for TCS.
- Godel, Escher Bach: An Eternal Golden Braid by Douglas Hofstadter. Belongs at least as much to TCS as it does to AI. This book is the first exposure to TCS ideas for many people.
August 21, 2005, at 12:54 PM
by Luca Aceto
Changed lines 7-9 from:
- Computers Ltd: What they really can't do by David Harel.
This is a beautiful, well-written and enjoyable book. It presents with meticulous clarity the fundamental results of computability and complexity theory to a non-mathematical audience, and briefly surveys novel models of computation such as quantum computing and molecular computing. Harel also explains how the computational intractability of some problems can be put to good use in fields like public-key cryptography. There should be more books like this one!
to:
- Computers Ltd: What they really can't do by David Harel. This is a beautiful, well-written and enjoyable book. It presents with meticulous clarity the fundamental results of computability and complexity theory to a non-mathematical audience, and briefly surveys novel models of computation such as quantum computing and molecular computing. Harel also explains how the computational intractability of some problems can be put to good use in fields like public-key cryptography. There should be more books like this one!
August 21, 2005, at 12:39 PM
by Luca Aceto
Changed lines 8-9 from:
to:
This is a beautiful, well-written and enjoyable book. It presents with meticulous clarity the fundamental results of computability and complexity theory to a non-mathematical audience, and briefly surveys novel models of computation such as quantum computing and molecular computing. Harel also explains how the computational intractability of some problems can be put to good use in fields like public-key cryptography. There should be more books like this one!
August 19, 2005, at 01:29 PM
by Luca
Added lines 7-8:
- Computers Ltd: What they really can't do by David Harel.
August 18, 2005, at 03:30 PM
by Sanjeev Arora
Changed lines 47-49 from:
- An Introduction to Bioinformatics Algorithms by Jones and Pevzner. A good introduction to how the study of algorithms has greatly shaped the course of Biology in recent decades. Also has good writeups about some of the leading figures from TCS in bioinformatics, including Karp, Myers, and Haussler.
to:
- An Introduction to Bioinformatics Algorithms by Jones and Pevzner. A good introduction to how the study of algorithms has shaped the course of Biology in recent decades. Also has good biopics of some of the leading figures from TCS in bioinformatics, including Karp, Myers, and Haussler.
August 18, 2005, at 03:28 PM
by Sanjeev Arora
Changed lines 47-49 from:
to:
- An Introduction to Bioinformatics Algorithms by Jones and Pevzner. A good introduction to how the study of algorithms has greatly shaped the course of Biology in recent decades. Also has good writeups about some of the leading figures from TCS in bioinformatics, including Karp, Myers, and Haussler.
August 05, 2005, at 06:42 PM
by Maverick Woo
Changed lines 7-8 from:
- The Advent of the Algorithm: The Idea That Rules The World by David Berlinski. Popular book that covers the emergence of the algorithm as a separate concept, with a historical focus on such figures as Frege and Turing. I personally (-David Molnar) do not care for it, but it is a popular work that treats TCS directly. (Scott Aaronson: David, I'd go further, and describe this book as a pompous, grandiloquent piece of garbage. It's a clear demonstration of why we need to popularize TCS ourselves: because otherwise the Berlinskis will rush in to fill the void.)
to:
- The Advent of the Algorithm: The Idea That Rules The World by David Berlinski. Popular book that covers the emergence of the algorithm as a separate concept, with a historical focus on such figures as Frege and Turing. I personally (-David Molnar) do not care for it, but it is a popular work that treats TCS directly.
(Scott Aaronson: David, I'd go further, and describe this book as a pompous, grandiloquent piece of garbage. It's a clear demonstration of why we need to popularize TCS ourselves: because otherwise the Berlinskis will rush in to fill the void.)
(Maverick Woo: I also agree that better general books should be and could be written. But what has popularization done to the funding situation of the Math community? (They actually do a great job in having general science books in Math.) Did it help? Does it achieve the level of funding that the Math community wants? If TCS do the same, would it be any different?)
July 28, 2005, at 06:12 PM
by Lance
Changed lines 7-14 from:
- The Advent of the Algorithm: The Idea That Rules The World by David Berlinski. Popular book that covers the emergence of the algorithm as a separate concept, with a historical focus on such figures as Frege and Turing. I personally (-David Molnar) do not care for it, but it is a popular work that treats TCS directly. (Scott Aaronson: David, I'd go further, and describe this book as a pompous, grandiloquent piece of garbage. It's a clear demonstration of why we need to popularize TCS ourselves: because otherwise the Berlinskis will rush in to fill the void.)
- Algorithmics: The Spirit of Computing by David Harel and Yishai Feldman. From the Amazon page: "First published in 1987, explains the basic ideas of algorithms, their structures, and how they manipulate data in computer programs. Of interest to programmers, systems analysts and designers, and software engineers, but the technical level is low enough to be accessible to readers with almost no mathematics or computer background." Makes it sound like a version of _What Is Mathematics?_ for TCS.
- Godel, Escher Bach: An Eternal Golden Braid by Douglas Hofstadter. Belongs at least as much to TCS as it does to AI. This book is the first exposure to TCS ideas for many people.
For high-school students
to:
- The Advent of the Algorithm: The Idea That Rules The World by David Berlinski. Popular book that covers the emergence of the algorithm as a separate concept, with a historical focus on such figures as Frege and Turing. I personally (-David Molnar) do not care for it, but it is a popular work that treats TCS directly. (Scott Aaronson: David, I'd go further, and describe this book as a pompous, grandiloquent piece of garbage. It's a clear demonstration of why we need to popularize TCS ourselves: because otherwise the Berlinskis will rush in to fill the void.)
- Algorithmics: The Spirit of Computing by David Harel and Yishai Feldman. From the Amazon page: "First published in 1987, explains the basic ideas of algorithms, their structures, and how they manipulate data in computer programs. Of interest to programmers, systems analysts and designers, and software engineers, but the technical level is low enough to be accessible to readers with almost no mathematics or computer background." Makes it sound like a version of _What Is Mathematics?_ for TCS.
- Godel, Escher Bach: An Eternal Golden Braid by Douglas Hofstadter. Belongs at least as much to TCS as it does to AI. This book is the first exposure to TCS ideas for many people.
For high-school students (and younger)
Changed lines 23-24 from:
- Computer Scientists Optimize Innovative Ad Auction by Sara Robinson
to:
- Computer Scientists Optimize Innovative Ad Auction by Sara Robinson
Added lines 33-34:
- Computer Science Unplugged by Tim Bell, Ian H. Witten and Mike Fellows. A number of games designed to teach a variety of mostly TCS concepts.
July 18, 2005, at 04:31 AM
by 129.97.192.176
Changed lines 7-8 from:
- The Advent of the Algorithm: The Idea That Rules The World by David Berlinski. Popular book that covers the emergence of the algorithm as a separate concept, with a historical focus on such figures as Frege and Turing. I personally (-David Molnar) do not care for it, but it is a popular work that treats TCS directly.
to:
- The Advent of the Algorithm: The Idea That Rules The World by David Berlinski. Popular book that covers the emergence of the algorithm as a separate concept, with a historical focus on such figures as Frege and Turing. I personally (-David Molnar) do not care for it, but it is a popular work that treats TCS directly. (Scott Aaronson: David, I'd go further, and describe this book as a pompous, grandiloquent piece of garbage. It's a clear demonstration of why we need to popularize TCS ourselves: because otherwise the Berlinskis will rush in to fill the void.)
July 15, 2005, at 10:52 PM
by 128.32.35.162
Added lines 11-12:
- Godel, Escher Bach: An Eternal Golden Braid by Douglas Hofstadter. Belongs at least as much to TCS as it does to AI. This book is the first exposure to TCS ideas for many people.
June 30, 2005, at 10:53 PM
by 216.27.180.116
Changed lines 23-25 from:
- Richard Kaye's Minesweeper NP-Completeness Pages
Web page and associated articles that introduce the notion of NP-completeness and show that "Minesweeper is NP-complete." Minsweeper the focus for a series of popular lectures by Ian Stewart on NP-completeness in 2000 connected with the Clay Mathematics Institute. Includes a link to a talk about the result and a followup article, but unfortunately not the original Mathematical Intelligencer article.
to:
- Richard Kaye's Minesweeper NP-Completeness Pages
Web page and associated articles that introduce the notion of NP-completeness and show that "Minesweeper is NP-complete." Minsweeper was the focus in 2000 for a series of popular lectures by Ian Stewart on NP-completeness connected with the Clay Mathematics Institute. Includes a link to a talk about the result and a followup article, but unfortunately not the original Mathematical Intelligencer article.
June 30, 2005, at 10:52 PM
by 216.27.180.116
Changed line 23 from:
- Richard Kaye's Minesweeper NP-Completeness Pages \\
to:
- Richard Kaye's Minesweeper NP-Completeness Pages
June 30, 2005, at 10:52 PM
by 216.27.180.116
Changed lines 9-10 from:
- [[http://www.amazon.com/exec/obidos/tg/detail/-/0321117840/qid=1120185255/sr=8-2/ref=sr_8_xs_ap_i2_xgl14/104-9315524-7509513?v=glance&s=books&n=507846 | Algorithmics: The Spirit of Computing} by David Harel and Yishai Feldman. From the Amazon page: "First published in 1987, explains the basic ideas of algorithms, their structures, and how they manipulate data in computer programs. Of interest to programmers, systems analysts and designers, and software engineers, but the technical level is low enough to be accessible to readers with almost no mathematics or computer background." Makes it sound like a version of _What Is Mathematics?_ for TCS.
to:
- Algorithmics: The Spirit of Computing by David Harel and Yishai Feldman. From the Amazon page: "First published in 1987, explains the basic ideas of algorithms, their structures, and how they manipulate data in computer programs. Of interest to programmers, systems analysts and designers, and software engineers, but the technical level is low enough to be accessible to readers with almost no mathematics or computer background." Makes it sound like a version of _What Is Mathematics?_ for TCS.
June 30, 2005, at 10:51 PM
by 216.27.180.116
Added lines 9-10:
- [[http://www.amazon.com/exec/obidos/tg/detail/-/0321117840/qid=1120185255/sr=8-2/ref=sr_8_xs_ap_i2_xgl14/104-9315524-7509513?v=glance&s=books&n=507846 | Algorithmics: The Spirit of Computing} by David Harel and Yishai Feldman. From the Amazon page: "First published in 1987, explains the basic ideas of algorithms, their structures, and how they manipulate data in computer programs. Of interest to programmers, systems analysts and designers, and software engineers, but the technical level is low enough to be accessible to readers with almost no mathematics or computer background." Makes it sound like a version of _What Is Mathematics?_ for TCS.
Added lines 23-30:
- Richard Kaye's Minesweeper NP-Completeness Pages \\
Web page and associated articles that introduce the notion of NP-completeness and show that "Minesweeper is NP-complete." Minsweeper the focus for a series of popular lectures by Ian Stewart on NP-completeness in 2000 connected with the Clay Mathematics Institute. Includes a link to a talk about the result and a followup article, but unfortunately not the original Mathematical Intelligencer article.
- How To Explain Zero-Knowledge Protocols To Your Children
Bedtime story that illustrates the notion of "simulator" used in cryptographic zero-knowledge proofs. Introduces the exceedingly clever Mick Ali as the descendant of Ali Baba. Beware: most people I try this on ask me "but why didn't Mick Ali just walk in one side of the cave and then walk out the other?" Replying "because that's how the math we are trying to allegorize actually works" is not so satisfying.
- Kid Krypto by Neal Koblitz. Article that discusses strategies for teaching "kid cryptography" to high school (and younger) students. Includes "Kid RSA," an averaging protocol secure against honest but curious kids, and "perfect codes." Also includes experience with trying out these ideas with actual high school students.
June 30, 2005, at 10:31 PM
by 216.27.180.116
Added lines 5-8:
Popular books (not aimed at students)
- The Advent of the Algorithm: The Idea That Rules The World by David Berlinski. Popular book that covers the emergence of the algorithm as a separate concept, with a historical focus on such figures as Frege and Turing. I personally (-David Molnar) do not care for it, but it is a popular work that treats TCS directly.
May 27, 2005, at 11:02 PM
by Luca
Changed line 28 from:
- A personal view of average-case complexity by Rusell Impagliazzo\\
to:
- A personal view of average-case complexity by Russell Impagliazzo\\
May 24, 2005, at 12:15 PM
by 130.49.222.38
Added lines 15-16:
- Computer Scientists Optimize Innovative Ad Auction by Sara Robinson
May 23, 2005, at 05:14 PM
by Suresh Venkat
Added lines 30-34:
Blogs
- The Computational Complexity Blog - complexity theory
- Ernie's 3D Pancakes - algorithms, geometry
- Vanity of Vanities, all is Vanity - algorithms, geometry
- The Geomblog - algorithms, geometry.
May 20, 2005, at 02:56 PM
by Luca
Changed lines 7-8 from:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg, SIAM News, Volume 37, Number 3, April 2004
A mathematical model of a social network that caputes the small world phenomenon of social networks and our ability to find "paths" in such networks.
to:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg, SIAM News, Volume 37, Number 3, April 2004
A mathematical model of social networks that caputes the small world phenomenon and our ability to find "paths" in such networks.
May 20, 2005, at 02:55 PM
by Luca
Changed lines 7-8 from:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg SIAM News, Volume 37, Number 3, April 2004
A mathematical model of a social network that caputes the small world phenomenon of social networks and our ability to find "paths" in such networks.
to:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg, SIAM News, Volume 37, Number 3, April 2004
A mathematical model of a social network that caputes the small world phenomenon of social networks and our ability to find "paths" in such networks.
May 20, 2005, at 02:55 PM
by Luca
Changed lines 7-8 from:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg SIAM News, Volume 37, Number 3, April 2004.\\ A mathematical model of a social network that caputes the small world phenomenon of social networks and our ability to find "paths" in such networks.
to:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg SIAM News, Volume 37, Number 3, April 2004
A mathematical model of a social network that caputes the small world phenomenon of social networks and our ability to find "paths" in such networks.
May 20, 2005, at 02:53 PM
by Luca
Changed lines 7-8 from:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg SIAM News, Volume 37, Number 3, April 2004\\ A mathematical model of a social network that caputes the small world phenomenon of social networks and our ability to find "paths" in such networks.
to:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg SIAM News, Volume 37, Number 3, April 2004.\\ A mathematical model of a social network that caputes the small world phenomenon of social networks and our ability to find "paths" in such networks.
May 20, 2005, at 02:53 PM
by Luca
Changed lines 7-9 from:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg SIAM News, Volume 37, Number 3, April 2004
A mathematical model of a social network that caputes the small world phenomenon of social networks and our ability to find "paths" in such networks.
to:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg SIAM News, Volume 37, Number 3, April 2004\\ A mathematical model of a social network that caputes the small world phenomenon of social networks and our ability to find "paths" in such networks.
May 20, 2005, at 02:52 PM
by Luca
Changed line 7 from:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg 'SIAM News', Volume 37, Number 3, April 2004\\
to:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg SIAM News, Volume 37, Number 3, April 2004
May 20, 2005, at 02:50 PM
by Luca
Added lines 7-9:
- The Small-World Phenomenon and Decentralized Search by Jon Kleinberg 'SIAM News', Volume 37, Number 3, April 2004\\
A mathematical model of a social network that caputes the small world phenomenon of social networks and our ability to find "paths" in such networks.
May 16, 2005, at 10:46 PM
by Luca
Changed line 7 from:
- Can you name the bigger number? by Scott Aaronson\\
to:
- Who can name the bigger number? by Scott Aaronson\\
May 16, 2005, at 10:40 PM
by Luca
Changed line 18 from:
- The history and status of the P vs NP question by Mike Sipser\\
to:
- The history and status of the P vs NP question by Mike Sipser\\
May 16, 2005, at 10:39 PM
by Luca
Changed lines 18-20 from:
- The history and status of the P vs NP question by Mike Sipser\\ It includes the famous letter of Godel to Von Neumann
to:
- The history and status of the P vs NP question by Mike Sipser\\
It includes the famous letter of Godel to Von Neumann
May 16, 2005, at 10:39 PM
by Luca
Changed lines 18-20 from:
- The history and status of the P vs NP question by Mike Sipser It includes the famous letter of Godel to Von Neumann
to:
- The history and status of the P vs NP question by Mike Sipser\\ It includes the famous letter of Godel to Von Neumann
May 16, 2005, at 10:38 PM
by Luca
Changed lines 3-4 from:
Click on the edit button to add more references to this page.
to:
Click the edit button to add more references to this page.
May 16, 2005, at 10:38 PM
by Luca
Added lines 3-4:
Click on the edit button to add more references to this page.
Deleted lines 26-28:
More...
Add your suggestions of titles that should be on this page by clicking on the edit button.
May 16, 2005, at 08:19 PM
by Luca
Changed lines 22-25 from:
From Pessiland to Algorithmica, a tour of the five possible worlds that result
from the possible answers to various open questions in complexity theory.
to:
From Pessiland to Algorithmica, a tour of the five possible worlds that result from the possible answers to various open questions in complexity theory.
May 16, 2005, at 08:15 PM
by Luca
Changed line 28 from:
Add your suggestions of titles that should be on this page by clicking on the edit button.
to:
Add your suggestions of titles that should be on this page by clicking on the edit button.
May 16, 2005, at 08:14 PM
by Luca
Changed lines 16-30 from:
<p>
<li> <a href="http://www.cs.berkeley.edu/~luca/cs172/sipser92history.pdf">The history and status
of the P vs NP question</a> by <a href="http://www-math.mit.edu/~sipser/">Mike Sipser</a><br>
It includes the famous letter of Godel to Von Neumann</li>
</ul>
<h2>Research-oriented:</h2>
<ul>
<li> <a href="http://www-cse.ucsd.edu/~russell/average.ps">A personal view of average-case complexity</a>
by <a href="http://www-cse.ucsd.edu/~russell/">Rusell Impagliazzo</a><br>
to:
- The history and status of the P vs NP question by Mike Sipser It includes the famous letter of Godel to Von Neumann
Research-oriented
- A personal view of average-case complexity by Rusell Impagliazzo\\
Changed lines 23-29 from:
from the possible answers to various open questions in complexity theory.</li>
</ul>
<h2>More...</h2>
Send your suggestions of titles that should be on this page
to <a href="comments@theorymatters.org">comments@theorymatters.org</a>
to:
from the possible answers to various open questions in complexity theory.
More...
Add your suggestions of titles that should be on this page by clicking on the edit button.
May 16, 2005, at 08:11 PM
by Luca
Deleted lines 4-5:
Added lines 11-22:
For undergraduates
- NP-completeness: A retrospective by Christos Papadimitriou
In 1995, a library search found that 6,000 papers a year were published with ``NP-complete'' in their title, abstract or list of keywords. In 2005, a Google search finds in excess of 300,000 hits. What makes this notion so useful and ubiquitous?
<p>
<li> <a href="http://www.cs.berkeley.edu/~luca/cs172/sipser92history.pdf">The history and status
of the P vs NP question</a> by <a href="http://www-math.mit.edu/~sipser/">Mike Sipser</a><br>
It includes the famous letter of Godel to Von Neumann</li>
Changed lines 25-26 from:
<h2>For undergraduates:</h2>
to:
<h2>Research-oriented:</h2>
Changed lines 29-43 from:
<li> <a href="http://www.cs.berkeley.edu/~christos/retro.ps">NP-completeness: A retrospective</a>
by <a href="http://www.cs.berkeley.edu/~christos/">Christos Papadimitriou</a><br>
In 1995, a library search found that 6,000 papers a year were published with ``NP-complete'' in their
title, abstract or list of keywords. In 2005, a <a href="http://www.google.com/search?q=NP-complete">Google
search</a> finds in excess of 300,000 hits. What makes this notion so useful and ubiquitous?
</li>
<p>
<li> <a href="http://www.cs.berkeley.edu/~luca/cs172/sipser92history.pdf">The history and status
of the P vs NP question</a> by <a href="http://www-math.mit.edu/~sipser/">Mike Sipser</a><br>
It includes the famous letter of Godel to Von Neumann</li>
to:
<li> <a href="http://www-cse.ucsd.edu/~russell/average.ps">A personal view of average-case complexity</a>
by <a href="http://www-cse.ucsd.edu/~russell/">Rusell Impagliazzo</a><br>
From Pessiland to Algorithmica, a tour of the five possible worlds that result
from the possible answers to various open questions in complexity theory.</li>
Deleted lines 35-45:
<h2>Research-oriented:</h2>
<ul>
<li> <a href="http://www-cse.ucsd.edu/~russell/average.ps">A personal view of average-case complexity</a>
by <a href="http://www-cse.ucsd.edu/~russell/">Rusell Impagliazzo</a><br>
From Pessiland to Algorithmica, a tour of the five possible worlds that result
from the possible answers to various open questions in complexity theory.</li>
</ul>
May 16, 2005, at 08:09 PM
by Luca
Changed line 7 from:
- Can you name the bigger number? by Scott Aaronson
to:
- Can you name the bigger number? by Scott Aaronson\\
Changed line 10 from:
- Quantum computing for high-school students by Scott Aaronson
to:
- Quantum computing for high-school students by Scott Aaronson\\
May 16, 2005, at 08:09 PM
by Luca
Changed lines 7-17 from:
- Can you name the bigger number? by Scott Aaronson
From a child's game to the definition of the Ackermann's function, the busy beaver problem,
the undecidability of the halting problem, and definability paradoxes.</li>
<p>
<li><a href="http://www.scottaaronson.com/writings/highschool.html">Quantum computing for high-school students</a>
by <a href="http://www.scottaaronson.com/">Scott Aaronson</a><br>
The title says it all.</li>
to:
- Can you name the bigger number? by Scott Aaronson
From a child's game to the definition of the Ackermann's function, the busy beaver problem, the undecidability of the halting problem, and definability paradoxes.
- Quantum computing for high-school students by Scott Aaronson
The title says it all.
May 16, 2005, at 08:08 PM
by Luca
Changed lines 7-8 from:
- Can you name the bigger number?
by Scott Aaronson\\
to:
- Can you name the bigger number? by Scott Aaronson\\
May 16, 2005, at 08:07 PM
by Luca
Added lines 1-55:
Survey Papers and Essays
For high-school students
- Can you name the bigger number?
by Scott Aaronson
From a child's game to the definition of the Ackermann's function, the busy beaver problem,
the undecidability of the halting problem, and definability paradoxes.</li>
<p>
<li><a href="http://www.scottaaronson.com/writings/highschool.html">Quantum computing for high-school students</a>
by <a href="http://www.scottaaronson.com/">Scott Aaronson</a><br>
The title says it all.</li>
</ul>
<h2>For undergraduates:</h2>
<ul>
<li> <a href="http://www.cs.berkeley.edu/~christos/retro.ps">NP-completeness: A retrospective</a>
by <a href="http://www.cs.berkeley.edu/~christos/">Christos Papadimitriou</a><br>
In 1995, a library search found that 6,000 papers a year were published with ``NP-complete'' in their
title, abstract or list of keywords. In 2005, a <a href="http://www.google.com/search?q=NP-complete">Google
search</a> finds in excess of 300,000 hits. What makes this notion so useful and ubiquitous?
</li>
<p>
<li> <a href="http://www.cs.berkeley.edu/~luca/cs172/sipser92history.pdf">The history and status
of the P vs NP question</a> by <a href="http://www-math.mit.edu/~sipser/">Mike Sipser</a><br>
It includes the famous letter of Godel to Von Neumann</li>
</ul>
<h2>Research-oriented:</h2>
<ul>
<li> <a href="http://www-cse.ucsd.edu/~russell/average.ps">A personal view of average-case complexity</a>
by <a href="http://www-cse.ucsd.edu/~russell/">Rusell Impagliazzo</a><br>
From Pessiland to Algorithmica, a tour of the five possible worlds that result
from the possible answers to various open questions in complexity theory.</li>
</ul>
<h2>More...</h2>
Send your suggestions of titles that should be on this page
to <a href="comments@theorymatters.org">comments@theorymatters.org</a>