Cook’s Paper

• Most Used Tags

  Algorithms amplification approximation award BDD Blum boolean breaking crypto-systems circuits Cook crypto-systems decision procedure deterministic diagonalize Diophantine Factoring Fermat FOCS formula graph Karp language lower bounds Machine matrix Nash nondeterminism NSF P=NP polynomial Presburger Problems Proof quantum Rabin random randomness SAT Simulation space stable stack sum of squares time Turing

• Search

• Subscribe to Gödel’s Lost Letter

  

• Follow on Twitter

  • Just posted on fifty years of FOCS. Come and predict the papers of FOCS 60th 1 month ago
  • Take a look at "Dancing with the Stars" at http://wp.me/BQFc Its a great new blog... 2 months ago
  • Just posted on world is digital at http://wp.me/r9Ir 2 months ago
  • last post made top 20 of wordpress...http://bit.ly/28U3BA 2 months ago
  • JUst posted recently on surprises in math/theory. take a look. http://wp.me/r9Ir 2 months ago

• Add Us to Your Favorites

  If you like Gödel Lost Letter, please go here and say so: thanks

• Translate

  Translate this blog into different languages...
  
  Albanian Arabic Bulgarian Catalan Chinese Simplified Chinese Traditional Croatian Czech Danish Dutch Estonian Filipino Finnish French Galician German Greek Hebrew Hindi Hungarian Indonesian Italian Japanese Korean Lativian Lithuanian Maltese Norwegian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swedish Thai Turkish Ukrainian Vietnamese

• Recent Posts

  • Is There a Test for Consciousness?
  • The Curious History of the Schwartz-Zippel Lemma
  • What Are Proofs For Anyway?
  • New Streaming Algorithms for Old Problems
  • Nash Equilibrium for Sparse Games: Part Deux
  • More on Mathematical Diseases
  • Rumors and Playing Games
  • On Mathematical Diseases
  • The Iceberg Effect in Theory Research
  • Highlights of FOCS Theory Day
  • Helping Wall Street Cheat With Theory
  • Happy Fiftieth Birthday FOCS
  • Multi-Party Protocols and FOCS 2009
  • Magical Results and P=NP
  • The Surprising Power of Rational Functions

• Top Posts

  • Is There a Test for Consciousness?
  • The Curious History of the Schwartz-Zippel Lemma
  • Highlights of FOCS Theory Day
  • What Will Happen When P≠NP Is Proved?
  • What Are Proofs For Anyway?
  • The Gödel Letter
  • About P=NP and SAT
  • About Me
  • Surprises in Mathematics and Theory
  • More on Mathematical Diseases

• Recent Comments

  	Personne on Is There a Test for Consc…
  	rjlipton on Is There a Test for Consc…
  	Personne on Is There a Test for Consc…
  	Josh on Is There a Test for Consc…
  	samt on Is There a Test for Consc…

• Blogroll

  • Algorithmic Game Theory
  • Computational Complexity
  • Equilibrium
  • Gil Kalai
  • Gowers’s Weblog
  • London Number Theory blog
  • Luca Trevisan
  • Martin Schwarz
  • Michael Mitzenmacher
  • Michael Nielsen
  • Microarray Blog
  • Oddly Shaped Pegs
  • Random bits
  • Scott Aaronson
  • Secret Blogging Seminar
  • Suresh Venkatasubramanian
  • tcs math
  • Terry Tao
  • The Algorithmic Lens
  • the polylogblog
  • The Unapologetic Mathematician
  • WWC
  • 

• Archives

  • December 2009
  • November 2009
  • October 2009
  • September 2009
  • August 2009
  • July 2009
  • June 2009
  • May 2009
  • April 2009
  • March 2009
  • February 2009
• To see this bigger go to my wordle page.

Blog at WordPress.com.

Theme: Vigilance by Jestro