Skip to content

An Agglomeration of links for 2011-03-11

Autum leaves on the beech tree, back yard  home in Falmouth, VALinks to ways to spend your money while traveling, a couple of links to the announcement of the 2011 Turing award, and a related link to a site about NP completeness

  • Repeatedly confounded by these questions, my wife, Joan, and I started to compile an informal rule book for what we call “econ-travel.” Rules are breakable, of course — and many of these have been — but by having them, I find myself less caught up in the decision-by-decision anguish of what to do.
  • Over the past 30 years, Leslie Valiant has made fundamental contributions to many aspects of theoretical computer science. His work has opened new frontiers, introduced ingenious new concepts, and presented results of great originality, depth, and beauty. Time and again, Valiant’s work has literally defined or transformed the computer science research landscape.
  • “Harvard University professor Leslie G. Valiant, a pioneer in the field of artificial intelligence, has been awarded the 2010 A.M. Turing Award, the most prestigious prize in the field of computer science. Valiant’s research into processes to make computers reason as humans do laid the groundwork for applications ranging from e-mail spam filters to IBM’s Watson computer system, which last month bested human competitors on the game show “Jeopardy!’’”
  • #P-complete, pronounced “sharp P complete,” is a complexity class in complexity theory. A problem is #P-complete if and only if it is in #P, and every problem in #P can be reduced to it by a polynomial-time counting reduction, i.e. a polynomial-time Turing reduction relating the cardinalities of solution sets. Very often the reductions are “parsimonious,” i.e., they preserve the number of solutions.

Post a Comment

Your email is never published nor shared. Required fields are marked *