• Where do journals go to die? https://blog.computationalcomplexity.org/2023/12/where-do-journals-go-to-die.html 22 comments 11/12/2023
• Where do non-primitive recursive functions come up naturally? https://blog.computationalcomplexity.org/2023/12/where-do-non-primitive-recursive.html 42 comments 4/12/2023
• How did people deal with punch cards? https://blog.computationalcomplexity.org/2023/11/in-bad-old-days-we-had-punchcards-how.html 183 comments 5/11/2023
• The “Debate” about Program Verif and the Lipton-Demillo-Perlis Paper (2021) https://blog.computationalcomplexity.org/2021/06/i-went-to-debate-about-program-verif.html 2 comments 25/2/2023
• Who first thought of the notion of Polynomial Time? http://blog.computationalcomplexity.org/2022/11/who-first-thought-of-notion-of.html 10 comments 15/11/2022
• Do computers make us more safe or less safe? https://blog.computationalcomplexity.org/2020/07/do-computers-make-us-more-safe-or-less.html 5 comments 27/7/2020
• A non-moral dilemma about cheating, but it brings up some points (2019) https://blog.computationalcomplexity.org/2019/11/a-non-moral-dilemma-about-cheating-but.html 134 comments 13/5/2020
• Richard Karp: His influence and how to honor him https://blog.computationalcomplexity.org/2019/03/richard-karp-his-influence-and-how-to.html 3 comments 10/3/2019
• BQP Not in the Polynomial-Time Hierarchy in Relativized Worlds https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.html 5 comments 2/6/2018
• NP is Hard http://blog.computationalcomplexity.org/2018/02/np-is-hard.html 2 comments 24/2/2018
• Will Our Understanding of Math Deteriorate Over Time? http://blog.computationalcomplexity.org/2015/07/will-our-understanding-of-math.html 71 comments 9/7/2015
• Polynomial-Time Hierarchy Is Infinite Under a Random Oracle http://blog.computationalcomplexity.org/2015/04/ph-infinite-under-random-oracle.html 11 comments 22/4/2015
• Is 99.8% secure secure? http://blog.computationalcomplexity.org/2012/02/is-998-secure-secure.html 2 comments 27/2/2012
• The 17x17 problem solved http://blog.computationalcomplexity.org/2012/02/17x17-problem-solved-also-18x18.html 37 comments 12/2/2012
• Drowning in Data: sometimes it's cheaper to recompute http://blog.computationalcomplexity.org/2010/07/drowning-in-data.html 4 comments 7/7/2010
• On Being Narrow http://blog.computationalcomplexity.org/2009/10/on-being-narrow.html 12 comments 2/10/2009
• Are top CS theorists nice people? Would they even talk with you? (comment 25) http://blog.computationalcomplexity.org/2009/09/why-you-shouldn-not-go-to-focs.html 48 comments 22/9/2009
• You Will All Work for Google http://blog.computationalcomplexity.org/2009/09/you-will-all-work-for-google.html 2 comments 18/9/2009
• Zero-Knowledge Sudoku: Verifying solution without looking at it. http://blog.computationalcomplexity.org/2006/08/zero-knowledge-sudoku.html 11 comments 27/5/2009

• You Need Much Less Memory than Time https://blog.computationalcomplexity.org/2025/02/you-need-much-less-memory-than-time.html 7 comments 4/3/2025 compsci
• In the bad old days we had punch cards. How did people deal with that? https://blog.computationalcomplexity.org/2023/11/in-bad-old-days-we-had-punchcards-how.html 10 comments 7/11/2023 historical

• In the bad old days we had Punchcards. How did people deal with that? https://blog.computationalcomplexity.org/2023/11/in-bad-old-days-we-had-punchcards-how.html 7 comments 18/11/2023 fortran
• "When does n divide a_n in this sequence?" (A suggestive pattern involving primes and a recurrence relation) http://blog.computationalcomplexity.org/2016/06/when-does-n-divide-in-this-sequence.html 13 comments 15/6/2016 math
• Will Our Understanding of Math Deteriorate Over Time? http://blog.computationalcomplexity.org/2015/07/will-our-understanding-of-math.html 6 comments 9/7/2015 math
• The Change Problem and the Gap between Recreational and Serious Mathematics http://blog.computationalcomplexity.org/2014/07/the-change-problem-and-gap-between.html 9 comments 28/7/2014 math
• Computational Complexity: What if P = NP? http://blog.computationalcomplexity.org/2004/05/what-if-p-np.html 11 comments 14/2/2013 compsci
• Maximum Flow in O(nm) Time http://blog.computationalcomplexity.org/2012/11/andrew-goldberg-guest-blog-on-new-max.html?utm_source=twitterfeed&utm_medium=twitter 23 comments 8/11/2012 compsci
• Computational Complexity: What happened to the Parallel Random Access Machine? http://blog.computationalcomplexity.org/2005/04/what-happened-to-pram.html 10 comments 13/9/2012 compsci
• Do 50-1 longshots in the Kentucky Derby ever come in? http://blog.computationalcomplexity.org/2012/06/do-50-1-longshots-in-kentucky-derby.html 6 comments 14/6/2012 statistics
• 17x17 problem solved (also, 18x18) http://blog.computationalcomplexity.org/2012/02/17x17-problem-solved-also-18x18.html 9 comments 8/2/2012 compsci
• What did Banach's Wife think of the Banach-Tarski Paradox? http://blog.computationalcomplexity.org/2011/04/what-did-banachs-wife-think-of-banach.html 46 comments 23/4/2011 math
• America's Most Important Algorithm http://blog.computationalcomplexity.org/2010/12/americas-most-important-algorithm.html 16 comments 7/4/2011 compsci
• What should everyone know? What does everyone know? http://blog.computationalcomplexity.org/2010/05/what-did-he-know-and-when-did-he-know.html 5 comments 12/5/2010 math
• Computational Complexity: Theorems that you simply don't believe http://blog.computationalcomplexity.org/2010/03/theorems-that-you-simply-dont-believe.html 21 comments 11/3/2010 math
• The First pseudorandom generator (Probably) 1240 AD http://blog.computationalcomplexity.org/2010/01/first-pseudorandom-generator-probably.html 3 comments 26/1/2010 math
• Ask a question on the internet get a 48 year old answer http://blog.computationalcomplexity.org/2009/12/hard-problem-inspired-by-easy-problem.html?showcomment=126106614565 17 comments 17/12/2009 math
• Is posting about 17x17 problem bad for academia? http://blog.computationalcomplexity.org/2009/12/is-posting-about-17x17-problem-bad-for.html 9 comments 9/12/2009 math
• 17x17: Comments on your comments http://blog.computationalcomplexity.org/2009/12/17x17-comments-on-your-comments.html 11 comments 2/12/2009 programming
• The 17x17 coloring challenge. Worth $289.00. http://blog.computationalcomplexity.org/2009/11/17x17-challenge-worth-28900-this-is-not.html 99 comments 30/11/2009 programming
• The 17x17 coloring challenge. Worth $289.00. http://blog.computationalcomplexity.org/2009/11/17x17-challenge-worth-28900-this-is-not.html 27 comments 30/11/2009 math