The Curious Engineer

All blogs / Math

Gödel's Lost Letter and P=NP

rjlipton.com

a personal view of the theory of computation

MathAlgorithms / data structuresComputing history

’10’15’20’25
Posts
1,155 from 12 Feb 2009 to 3 May 2026
Posting
now and then (2 in the last year)
Kind
personal blog
Feed
https://rjlipton.com/feed/

2026 2

  1. A Question
  2. Rabin has just passed away

2024 38

  1. Women In Theory
  2. Biblical Codes
  3. Foundations of Computer Science
  4. Guess Which Way?
  5. Fulkerson Prize
  6. Planar Graphs—Again
  7. FOCS 2024
  8. Gordon Bell
  9. A Most Important Number
  10. Quantum Computers on Wall Street
  11. The 100th anniversary of Fulkerson’s Birthday
  12. Just Jim
  13. COMPUTATION, LOGIC, AND INFORMATION
  14. Frontiers in Complexity Theory
  15. 1968 vs 2024
  16. Science Section
  17. An Open Problem
  18. Women in Math Research
  19. Guggenheim 2024
  20. 2023 Turing Award
  21. The Coming Solar Eclipse
  22. Daniel Kahneman, 1934–2024
  23. Quantum Unproving
  24. STOC 2024
  25. Leprechauns Sue Over AI
  26. Does Pi Conspire?
  27. P=NP and Bitcoin
  28. Dominic Welsh, 1938–2023
  29. Structure of Polynomials
  30. New Methods Solve Old Problems
  31. Stop Cheating—Again
  32. Congrads to NAE’24
  33. Predictions 2024
  34. Some Fun Today
  35. A Talk at TTIC on Experiment Design
  36. The Turing Award Winner Speaker Series
  37. ICTS 2024 — Innovations in Theoretical Computer Science
  38. One Day, Three Stories

2023 62

  1. Things We Did Not Know How to Compute
  2. Harvard’s View of Plagiarizing
  3. Have I Been Cheating at Wordle?
  4. Numbers Too Big for Our Universe
  5. Thanks to Will Shortz
  6. Kurt Gödel In The Movies
  7. Is P=NP a Grave Matter?
  8. A Conference At TTIC
  9. Fairness and Sampling
  10. Possible Impossibilities and Impossible Possibilities
  11. Generating Functions and Singularities
  12. 2023 NAE Meeting
  13. Four and More Colors of Mathematics
  14. 2023 NAE Meeting
  15. Happy Birthday 77
  16. Congrats to Three Colleagues
  17. The Distributed Prize
  18. Should These Quantities Be Linear?
  19. TTIC Makes a Hire
  20. Two Other Tests of Time
  21. FOCS Test of Time Awards
  22. Independence Day 2046?
  23. A New AKS
  24. AI Ends It All
  25. A Hidden Heroine
  26. Computer Science Marches On
  27. A Little Noise Makes Quantum Factoring Fail
  28. Human Extinction?
  29. Topping the Hat
  30. Combinatorics or Logic?
  31. Early Theory
  32. Ingrid Daubechies: Prizes and Art
  33. A TTIC Talk
  34. Isbell Accepts
  35. Dark Silicon
  36. Some Rice News
  37. An Award For Ellen Zegura
  38. Schoolbook Error/Discovery
  39. ACM Prize to Yael Kalai
  40. Neil Jones, 1941–2023
  41. The ChatGPT Conundrum
  42. A New Tiling
  43. William Wulf, 1939–2023
  44. The 2022 Turing Award
  45. Problems Better Than Solutions
  46. Céad Míle GPT
  47. Is Pi Informative?
  48. STACS 2023
  49. SODA 2023
  50. STOC 2023
  51. Thanks to Rich
  52. Novel Proofs of the Infinitude of Primes
  53. Are We Nuts?
  54. FOCS 2022 Program
  55. Back From A Vacation
  56. Artificial Intelligence Just Lost a Leader
  57. Why Study Logic?
  58. Rabin-Scott Time
  59. Art as Math that Meets Crochet
  60. Cargo Cult Redo
  61. Logicians are Everywhere
  62. From the Previous ’20s Decade to This One

2022 47

  1. The Gift of Nonconstructivity
  2. Fusion Breakthrough or Increment?
  3. A Mutation Carol 2
  4. Thanks 2
  5. Quantum Circuits in the New York Times
  6. The Gerrymanders Have It
  7. Cheating at Chess—Not Again
  8. Legal Complexity
  9. A Theoretical Question About UAPs
  10. Juris Hartmanis 1928–2022
  11. Complexity 2022
  12. The Fallows of Medium Data
  13. The Graph of Ancestors
  14. Sorting and Proving
  15. Laws and Laughs
  16. Women In Theory
  17. Easy as ABC
  18. CCC 2022 Conference
  19. Being Different
  20. Hilbert’s Lost Problem
  21. Take Wing
  22. Rafail Is No Secret
  23. Differential Privacy
  24. Peter’s Face
  25. Sedgewick to Emeritus Status
  26. Math Monthly
  27. A Paradox
  28. Discussion About Proving—Again
  29. Blogs that are Current
  30. An Ozone Hole in Logic
  31. The 2021 Turing Award
  32. Waiting For Self-Deriving Cars
  33. Meta Wishes
  34. Are These the Last Digits of Pi?
  35. I Am Now A Cyberman
  36. ACM: Celebrating 75 Years
  37. Simons Awards for 2022
  38. Inequalities on the Gridiron
  39. National Academy of Engineering Elects
  40. Next Big Thing?
  41. Bill Gasarch Also 1,000
  42. A List of Most Theory Blogs
  43. Cheating In Chess
  44. Dinner! Drinks! Denominators!
  45. Zoom Workshop E-Minder: 4pm ET Today
  46. Happy 1,000th Post and 75th Birthday, Dick
  47. Quantum Graph Theory

2021 64

  1. Make A Trillion Dollars
  2. Favorite Theorems of the Next Ten Years
  3. The New Journal
  4. Best To Dean Mynatt
  5. POPL 2022—Et Tu, Brute?
  6. The Artificial Intelligence Historian
  7. Quantum Trick or Treat
  8. An Annoying Problem
  9. Some Statistical Gamma Fun
  10. Physics Nobel Prize for 2021
  11. Baby Steps
  12. A Possible Ramsey Insight into P Versus NP?
  13. Happy UnBirthday Ken
  14. Texas-Sized Problems
  15. Great Go, Glitchy Grammar
  16. A Negative Comment on Negations
  17. P vs NP Proof Claims
  18. Turning the Tables on Cheating?
  19. Pandemic Lag
  20. The Reach of Dichotomy
  21. Socially Reproduced Experiments
  22. Scaling and Fame
  23. The Shape of This Summer
  24. Thursday—June 17th—A Debate on Program Correctness
  25. Tardos Is Off With Good Behavior
  26. Happy Mom’s Day
  27. The Voting Paradox
  28. ACM Athena Lecturer Award
  29. Hilbert Tenth On Rationals
  30. Matrix—The Meeting
  31. How to Teach Math?
  32. Test of Time
  33. Congrats to the New Members
  34. Ken Turns 40
  35. Summing Up the Primes
  36. Scott Wins a Prize
  37. Wobble in the Standard Model
  38. Relaxing the Primes
  39. Computer Science Gets Noted
  40. All The News That Fits We Print
  41. Congrats Avi and Laci on the Abel Prize
  42. Moby Dick Meet Theory
  43. Closing an Erdős Problem
  44. Happy St. Patrick’s Day 2021
  45. The Value of Pi
  46. Hilbert’s Tenth Again
  47. Making Algorithms Fair
  48. Advancing and Counting
  49. WSJ Meets Group Algorithms
  50. New, Old, Ancient Results
  51. A Quiz of Quotes
  52. Riemann Hypothesis—Why So Hard?
  53. Computing’s Role In The Pandemic
  54. Alan Selman
  55. Pigeonhole Principle
  56. Pigenhole Principle
  57. Graph Products
  58. Alan Selman, 1941–2021
  59. Happy Un-Birthday Rich
  60. Science Advisor
  61. Edmund Clarke, 1945–2020
  62. Priming Random Restrictions
  63. Predictions For 2021
  64. Peter M. Neumann, 1940–2020

2020 68

  1. P < NP In Our Stockings?
  2. Database and Theory
  3. Is The End Near?
  4. The Future of Mathematics?
  5. Too Long, Didn’t Read
  6. Traveling Salesman Problem Meets Complexity Theory
  7. The Art of Math
  8. The Election Night Time Warp
  9. The Night of the Ethical Algorithm
  10. A Vast and Tiny Breakthrough
  11. Can We Solve It?
  12. Vaccines are Not Developing
  13. Are Black Holes Necessary?
  14. Knowledge is Good
  15. IBM Conference on the Informational Lens
  16. Puzzle Reviews by a Puzzle Writer
  17. Ken Regan Turned 61
  18. Convex Algorithms
  19. Hybrid Versus Remote Teaching
  20. Closing An Open Problem
  21. Mea Culpa
  22. 20,000 Comments and More
  23. Logical Complexity of Proofs
  24. Thanks to An Explainer
  25. Fran Allen: 1932-2020
  26. Cleverer Automata Exist
  27. A Brilliant Book on Combinatorics
  28. Mathematical Search
  29. Ron Graham, 1935–2020
  30. Intellectual Fireworks?
  31. Taking a Problem Down a Peg
  32. Some Real and Some Virtual News
  33. Pnp
  34. Proof Checking: Not Line by Line
  35. The Doomsday Argument in Chess
  36. The Truth
  37. Just Arvind
  38. Proof of the Diagonal Lemma in Logic
  39. Math Tells
  40. The 2020 Y Prize
  41. Consistency and P=NP
  42. Mathematics of COVID-19
  43. Time For Some Jokes
  44. Proof and Cake Envy
  45. John Horton Conway 1937–2020
  46. Nina Balcan Wins
  47. Not As Easy As ABC
  48. Research at Home
  49. Logic and Star-Free, Part Deux
  50. Star-Free Regular Languages and Logic
  51. Leprechauns Stay Home
  52. Group Testing For The Coronavirus
  53. The Virtue of Closed Problems
  54. Dyson as a Mathematician
  55. Reductions and Jokes
  56. Should We Teach Coding in High School?
  57. P=NP: A Story
  58. A Beetle Math Puzzle
  59. Using Negative Nodes to Count
  60. Counting Votes By Humans
  61. Tricks of The Trade
  62. Subliminal Graph Duals
  63. The Halting No Go Theorem
  64. Predicting Predictions For the 20s
  65. Halting Is Poly-Time Quantum Provable
  66. Our Thoughts on P=NP
  67. No Password Encryption
  68. Servant: The TV Show

2019 65

  1. Resolutions For 2020
  2. A Math Gift For All
  3. Predicting When P=NP is Resolved
  4. An Ancient Conjecture on Primes
  5. Héctor Garcia-Molina, 1953–2019
  6. End-to-End Encryption: A Problem
  7. Predicating Predictivity
  8. A Clever Way To Find Compiler Bugs
  9. Goldbach: A Curious Conjecture
  10. Hobgoblins in Our Equations
  11. Quantum Supremacy At Last?
  12. A Polemical Overreach?
  13. A Diophantine Obvious Problem
  14. Writing 33 as a Sum of Cubes
  15. Quantum Switch-Em
  16. Separating Words: Decoding a Paper
  17. Separating Words by Automata
  18. Self-Play Is Key?
  19. Danny Cohen Passed Away
  20. A Matroid-Quantum Connection
  21. Our Trip To Monte Carlo
  22. Predicting Chess and Horses
  23. Leaps and Bounds: Practice Meets Theory
  24. Code It Up
  25. The Electoral College: Is It Good?
  26. Discrepancy Games and Sensitivity
  27. Summer Reading in Theory
  28. Tools and Sensitivity
  29. Mathematics of Gerrymandering
  30. A Prime Breakthrough
  31. Computer Science Gender Gap
  32. Diophantine Equations
  33. Contraction and Explosion
  34. How To Make A Polynomial Map Nicer
  35. Net-Zero Graphs
  36. Raymond Edward Miller Just Passed Away
  37. A Rank Problem
  38. A Quantum Connection For Matrix Rank
  39. Selected Papers at CCC 2019
  40. Making Up Tests
  41. An App Proof
  42. Internet, Dogs, and the ABC Conjecture
  43. Making Elections Safe
  44. The Network Coding Conjecture Is Powerful
  45. Sedgewick Wins An Award
  46. Network Coding Yields Lower Bounds
  47. Why Check A Proof?
  48. P=NP Proofs
  49. A Reason Why Circuit Lower Bounds Are Hard
  50. Seeing Is Believing
  51. Avi Wins The Knuth Prize
  52. The Breakthrough Result Of 2019
  53. Integer Multiplication in NlogN Time
  54. The Shortest Path To The Abel Prize
  55. Leprechauns Go Universal
  56. Problems With a Point
  57. Phrases That Drive Me Crazy
  58. Making A Mapping Injective
  59. Have Ten Years Brought Us Closer?
  60. An Old But Cool Result
  61. A Strange Horizon
  62. Primes And Polynomials
  63. A Simple Fact
  64. Jean Bourgain 1954–2018 and Michael Atiyah 1929–2019
  65. Predictions For 2019

2018 47

  1. ACM Great Results
  2. Explanations and Explorations
  3. Explaining The Jaccard Metric
  4. Transposing
  5. A Tiebreak Win and the Problem of Draws
  6. Far From a Turkey Shoot
  7. A Thanksgiving Treat
  8. A Mathematical Auction
  9. A Dumb Group Theory Question
  10. Micro Barriers To Diversity
  11. The Inscribed Square Problem
  12. London Calling
  13. Watching Over the Zeroes
  14. Reading Into Atiyah’s Proof
  15. Preview of the Atiyah Talk
  16. The Specter of Simple(r) Proofs
  17. Abelian Groups, Mostly
  18. Sliding-Scale Problems
  19. Limits On Matrix Multiplication
  20. Do You Want to Know a Secret?
  21. Power Circuits
  22. Winner Of 2018 Knuth Prize Is:
  23. Desperately Seeking Integers
  24. A Quest For Simple Hard Statements
  25. Group Theory Is Tough
  26. You Cannot Do That
  27. Local Hams in La Jolla
  28. Muffins and Integers
  29. Hilbert’s Irreducibility Theorem
  30. Princeton Is Invariant
  31. Almost Fermat Primes
  32. Does 1 Times 1 Equal 2?
  33. Lost in Complexity
  34. A New Proof Of An Ancient Result
  35. Finding Coprime Pairs
  36. Tom Lehrer At 90
  37. The Entropy of Baseball
  38. Is There Momentum in Chess?
  39. Leprechauns Know What It Feels
  40. Happy 0x50th Birthday, Donald Knuth
  41. The Lemma Cited From Burnside
  42. A Coup(e) of Duchamp
  43. Some Technical Tidbits
  44. Doing Mod N Via Mod R
  45. Progress on the Frontier
  46. Timing Leaks Everything
  47. Predictions We Didn’t Make

2017 35

  1. Truth From Zero?
  2. P=NP: Perhaps I Change My Mind
  3. Proving Peano Arithmetic Partially Consistent?
  4. A Magic Madison Visit
  5. Lotfi Zadeh 1921–2017
  6. Michael Cohen 1992-2017 and Vladimir Voevodsky 1966–2017
  7. Drama Therapy: A Math Viewpoint
  8. Happy Birthday Ken
  9. A TSP Breakthrough
  10. A Retirement Party for Joel Seiferas
  11. On the Edge of Eclipses and P=NP
  12. Modeling Reality
  13. Maryam Mirzakhani, 1977–2017
  14. Kitchen Tile Catalog Complete
  15. Eric and Mike Turn 60
  16. Oded Wins The Knuth Prize
  17. TOC In The Future
  18. Does Logic Apply To Hearings?
  19. Goldilocks Principle And P vs. NP
  20. Stopped Watches and Data Analytics
  21. A Mother’s Day Cryptogram?
  22. A Great Solution
  23. Theory Fest—Should You Go?
  24. Turing Award 2016
  25. The End Of Human Science?
  26. Gender Bias: It Is Worse Than You Think
  27. Leprechauns are Multiplying
  28. Is Computer Security Possible?
  29. Working Backward
  30. Raymond Smullyan, 1919–2017
  31. A Panel On P vs. NP
  32. How to Check a Proof
  33. Level By Level
  34. Snow And Theory
  35. Babai’s Result: Still a Breakthrough

2016 51

  1. The Gift of Community
  2. Hunting Complexity in Zeta
  3. Bletchley Park
  4. Magnus and the Turkey Grinder
  5. When Data Serves Turkey
  6. Thanks
  7. GLL At the Chess Match
  8. Unskewing the Election
  9. Halloween Math Style
  10. Absolute Firsts
  11. Going For Two
  12. Why Is Being Truthful A Good Thing?
  13. Congratulations, Noam
  14. A Creeping Model Of Computation
  15. A Proof Of The Halting Theorem
  16. How Hard, Really, is SAT?
  17. Descending Proofs Into Algorithms
  18. A Surprise For Big-Data Analytics
  19. Do results have a “teach-by-date?”
  20. The Mathematics Of Dan’s Inferno
  21. The World Turned Upside Down
  22. Getting to the Roots of Factoring
  23. Theory In The Time of Big Data
  24. Polynomial Prestidigitation
  25. Progress On Modular Computation
  26. Making Public Information Secret
  27. Coins on a Chessboard III
  28. Theory Meets Material Science
  29. Rejection
  30. Get A Job
  31. Quantum Supremacy and Complexity
  32. ARC Day At Georgia Tech
  33. Missing Mate in Ten
  34. The Primes Strike Again
  35. Bias In The Primes
  36. Happy St. Patrick’s Day
  37. One Flip Sends Many Bits
  38. Stonefight at the Goke Corral
  39. David Johnson: 1945-2016
  40. A Matter of Agreement
  41. The Pierce-Birkhoff Conjecture
  42. Coins on a Chessboard
  43. Waves, Hazards, and Guesses
  44. New NAE Members
  45. Magic To Do
  46. The 2016 Knuth Prize
  47. Failure Of Unique Factorization
  48. Minsky The Theorist
  49. A Chess Firewall at Zero?
  50. Did Euclid Really Mean ‘Random’?
  51. You Think We Have Problems

2015 58

  1. Blasts From the Past
  2. Why Is Discrete Math Hard To Teach?
  3. A Game On Infinite Trees
  4. Permutation Problems With Strings
  5. Thanks for Additivity
  6. A Little More on the Graph Isomorphism Algorithm
  7. A Fast Graph Isomorphism Algorithm
  8. The World Series Of Complexity Theory
  9. A Big Result On Graph Isomorphism
  10. Ghosts in Princeton
  11. Guessing Conjectures
  12. Rankings Versus Ratings
  13. Is The Hot Hand Fallacy A Fallacy?
  14. Ken Hits The Big Time
  15. Depth of Satisficing
  16. A Curious Inversion
  17. Frogs and Lily Pads and Discrepancy
  18. Taming Some Inequalities
  19. A Polynomial Growth Puzzle
  20. Open Problems That Might Be Easy
  21. How Joe Traub Beat the Street
  22. Cancellation is a Pain
  23. Cryptography And Quicksand
  24. Changing Definitions
  25. Four Weddings And A Puzzle
  26. Playing Chess With the Devil
  27. Alberto Apostolico, 1948–2015
  28. The Long Reach of Reachability
  29. The Halting Problem For Linear Machines
  30. We Say Branches And You Say Choices
  31. Fathering Randomized Fault Tolerance
  32. Security Via Surrender
  33. Minor Insights Are Useful
  34. Puzzling Evidence
  35. John and Alicia Nash, 1928,1933–2015
  36. The Shapes of Computations
  37. A Tighter Grip on Circuit Depth
  38. Transcomputational Problems
  39. The Anti-Pigeonhole Conjecture
  40. Case Against Cases
  41. Kinds of Continuity
  42. A Quantum Two-Finger Exercise
  43. April Fool
  44. Is It New?
  45. Leprechauns Will Find You
  46. The Other Pi Day
  47. Lint For Math
  48. News on Intermediate Problems
  49. The Right Stuff of Emptiness
  50. Ada the Amplifier
  51. Still A Brilliant Idea
  52. Cynthia Dwork and a Brilliant Idea
  53. Where Hard Meets Easy
  54. Why is Congruence Hard to Learn?
  55. A Computer Chess Analysis Interchange Format
  56. Forgetting Results
  57. There Are Many Primes
  58. Mathematics: It’s About the Future

2014 83

  1. The New Chess World Champion
  2. Modulating the Permanent
  3. Prover’s Block
  4. Chats
  5. Quantum Algorithms Via Linear Algebra
  6. Susan Horwitz 1955–2014
  7. Cornell CS at 50
  8. Two Versus Three
  9. Alexander Grothendieck 1928–2014
  10. Three In The Room
  11. A Conjecture Of Ulam
  12. DC Post
  13. Reconstructing Gödel
  14. Rebooting Computing
  15. A New Twist on Flexagons?
  16. A New Provable Factoring Algorithm
  17. TEDx Time In Buffalo
  18. More on Testing Dyson’s Conjecture
  19. How To Add Numbers
  20. The Busy Beaver Problem
  21. Microsoft Closes SVC
  22. Evolution: A Complexity View
  23. Let’s Mention Foundations
  24. Some Strange Math Facts
  25. A Challenge From Dyson
  26. Enriching the Frankl Conjecture
  27. Who Invented Pointers, Amortized Complexity, And More?
  28. Why Is 290 Special?
  29. The Derivative Of A Number
  30. The 3SUM Assumption Is Wrong?
  31. Our Three Body Problem
  32. Laplace’s Demon
  33. Diagonalization Without Sets
  34. The Cantor-Bernstein-Schröder Theorem
  35. An Old Galactic Result
  36. Shifts In Algorithm Design
  37. Constructive Sets
  38. High School Theorems
  39. Do Random Walks Help Avoid Fireworks?
  40. Remembering Ann Yasuhara
  41. A Pretty Identity
  42. Counting Edge Colorings Is Hard
  43. The Problem of Catching Chess Cheaters
  44. Honor Thy Fathers Correctly
  45. Proof Envy
  46. Is This a Proof?
  47. How To Avoid Leaving Clues
  48. Avoiding Monsters and Non-Monsters
  49. STOC 1500
  50. Lifting The Edge
  51. NEXP and the Next Generation
  52. The Easiest Impossible Problem
  53. Does Program Size Matter?
  54. Bell’s Fifty Year Old Mistake
  55. Galactic Sorting Networks
  56. In Praise Of P=NP Proofs
  57. The More Variables, the Better?
  58. Multiple-Credit Tests
  59. Counting Is Sometimes Easy
  60. Wait Wait… Don’t Fool Me!
  61. A Matchless Result
  62. Rabin Meets Lagrange
  63. The Power Of ACC
  64. Happy St. Patrick’s Day 2014
  65. Could We Have Felt Evidence For SDP ≠ P?
  66. How To Carry Fame
  67. Codes Meet Numbers
  68. Can Plants Do Arithmetic?
  69. Practically P=NP?
  70. The Evil Genius
  71. Three From CCC
  72. Seeing Atoms
  73. Black Versus White Boxes
  74. Regression On Arithmetic Progressions
  75. Global Warming?
  76. Progress On The Jacobian Conjecture
  77. Zack’s Mom Knows
  78. Anti-Social Networks
  79. Making Learning Less Shattering
  80. Bounds On Binomial Coefficents
  81. Details Left To The Reader…
  82. A Shameless Plug
  83. Predictions For The New Year

2013 77

  1. The Winner Is…
  2. Re-gifting An Old Theorem
  3. A Pardon For Alan Turing
  4. What Is Best Result Of The Year?
  5. Who Knew The Secret?
  6. A Negative Impossibility Theorem
  7. Judging A Book By Its Coverage
  8. Isomorphism Is Where It’s At
  9. Theorems From Physics?
  10. Finding Patterns In Ancient Objects
  11. The Graph of Math
  12. In Praise Of Chalk Talks
  13. A Really Scary Thought
  14. Pretending In Number Theory
  15. A Request That We Passed On
  16. Teaching Helps Research
  17. 512
  18. Proving Cook’s Theorem
  19. Rating FOCS 1973
  20. Stealing Strategies
  21. Two Bits About FOCS 2013
  22. A Dictionary For Reading Proofs
  23. Mary Jean Harrold
  24. Littlewood’s Law
  25. Teacher Teach Yourself
  26. Space Is Easier Than Time
  27. Euler’s Constants
  28. More on the Diagonal
  29. D Plus O Equals Do
  30. A World Without Randomness
  31. Euclid Strikes Back
  32. Move the Cheese
  33. Crypto Aspects of The Jacobian Conjecture
  34. Making Choices
  35. Thirteen Sigma
  36. Ghostbusting Old Factoring Ideas
  37. Surely You Are Joking?
  38. Rough Problems
  39. Independence Day
  40. Approximating Boolean Functions
  41. It Takes Guts To Do Research
  42. Three Theorems About Growth
  43. Happy Father’s Day
  44. The Mathematics Of Dieting
  45. Triads and Dyads
  46. Psst—It’s The Definition
  47. Why Is There Something?
  48. Kenneth and Laurel Appel, In Memoriam
  49. Twin Primes Are Useful
  50. Graduate Student Traps
  51. Advances on Group Isomorphism
  52. A Most Perplexing Mystery
  53. A Trillion Dollar Math Trick
  54. Happy Birthday, Kurt Gödel
  55. Sex, Lies, And Quantum Computers
  56. Can We Prove Better Independence Theorems?
  57. Subset Powers of Graphs
  58. Measures Are Better
  59. Zeno Proof Paradox
  60. Interstellar Quantum Computation
  61. Happy 100th Birthday, Paul Erdős
  62. Win Five Hundred Or A Million Dollars, By Recursion?
  63. The Thousand Percent Solution
  64. Happy St. Patrick’s Day—Again and Again and Again and Again
  65. No-Go Theorems
  66. Checking the Higgs Boson
  67. Cryptography Is Dead?
  68. Who Invented Boolean Functions?
  69. Adding Dollar Signs
  70. The Informatics Prize
  71. Polynomials Behaving Badly
  72. “Cantor” Video Quick Survey
  73. Making Primes More Random
  74. Cantor’s Theorem: The Movie
  75. The Crown Game Affair
  76. Back To The Past
  77. Predictions and Principles

2012 104

  1. The Year That Was
  2. Scientific Gifts
  3. What Would Be Left, If…?
  4. Branch And Bound—Why Does It Work?
  5. When Less Is More
  6. Mounting or Solving Open Problems
  7. The Amazing Zeta Code
  8. Barriers to P=NP Proofs
  9. Thanks For Sharing
  10. A Wonderful Riff On Rank
  11. Progress On Progressive Algorithms
  12. The Ryan Williams Combine
  13. The Power Of Guessing
  14. The Election Outcome
  15. More Interview With Kurt Gödel
  16. Mathematical Mischief Night
  17. Short and Tweet
  18. Algorithms At Oxford
  19. One Man’s Floor Is Another Man’s Ceiling
  20. My Thing About The “Thing” Movies
  21. What’s Blue and White and Red All Over?
  22. Quantum Supremacy or Classical Control?
  23. Why We Lose Sleep Some Nights
  24. How Not To Prove Integer Factoring Is In P
  25. What Is The Object?
  26. Might Turing Have Won A Turing Award?
  27. Quantum Repetition
  28. The ABC Conjecture And Cryptography
  29. Patching A Diagonalization
  30. Thinking Out of the Notation Box
  31. High School Trig Is Powerful
  32. Why Do Some Arguments Seem Wrong?
  33. Do We Need Mysticism In Theory?
  34. Do We Need Mysticism In Theory?
  35. Ten Years of Blog Complexity
  36. Cheating Or Mastering?
  37. The Right Definition
  38. The Speed of Communication
  39. A New Way To Solve Linear Equations
  40. Reading A Speech
  41. Michigan Coding, Complexity, and Sparsity Workshop
  42. Benford’s Law and Baseball
  43. Facts No One Really Checks
  44. How Good Is Your Translator?
  45. An Education Tsunami
  46. It Don’t Come EaSY
  47. Giants Known For Small Things
  48. Grilling Quantum Circuits
  49. July Fourth Sale Of Ideas
  50. Connect the Stars
  51. Area 51
  52. Happy Unbirthday To Turing
  53. Cricket, 400, and Complexity Theory
  54. Can You Hear the Shape of a Quantum Computer?
  55. Why The Hartmanis-Stearns Conjecture Is Still Open
  56. What Is Normal?
  57. Mihai Pătraşcu 1982–2012
  58. Transcendental Aspects of Turing Machines
  59. Proud Simons
  60. Chess Knightmare and Turing’s Dream
  61. Your Turing Test
  62. Beyond Las Vegas And Monte Carlo Algorithms
  63. Turing’s Tiger Birthday Party
  64. Quantum Refutations and Reproofs
  65. Inexact Remarks On Exact TSP Algorithms
  66. Digital Butterflies and PRGs
  67. A Thank-You to Jim Simons
  68. Cutting a Graph By the Numbers
  69. The Travelling Salesman’s Power
  70. Cybercrime And Bad Statistics
  71. Tabulation Hashing and Independence
  72. Lonely Runner Conjecture—A Second Attack
  73. A Lazy Approach To Problem Solving
  74. Introducing TechPlex.Com
  75. When is a Law “Natural”?
  76. Interdisciplinary Research—Challenges
  77. The Singularity Is Here In Chess
  78. Leprechauns Are Tricky
  79. How Good Is Your I-magination?
  80. A Note on Distributions and Approximation
  81. The Quantum Super-PAC
  82. Do Gaps Between Primes Affect RSA Keys?
  83. The Bourne Factor
  84. An Amazing Result
  85. Being Fearless And Doing Theory
  86. Insecure Provable Protocols
  87. Nature Does Not Conspire
  88. A Year of Posts
  89. Computational Topology
  90. How Deep is Your Coloring?
  91. Introducing Pip
  92. Is This A Quantum Computer?
  93. Flying Machines of the 21st Century?
  94. Lonely Runner Conjecture—An Attack
  95. Quantum Groundhog Day
  96. A Brief History Of Matrix Product
  97. Perpetual Motion of The 21st Century?
  98. The Lonely Runner Conjecture
  99. Ode To The Math Monthly
  100. Is it Time to Declare Victory in Counting Complexity?
  101. It’s Still the Slime Mold Story
  102. What Makes a Knot Knotty?
  103. 2012 Survey Results
  104. Predictions For 2012

2011 109

  1. A 2012 Survey
  2. The Name Game
  3. Proofs, Proofs, and Proofs
  4. …And To Make A Long Story Short—
  5. The Higgs Confidence Game
  6. A Lemma on Factoring
  7. Theorems Are Forever: A Great One From 1492
  8. The Meaning of Omega
  9. A Breakthrough On Matrix Product
  10. A Brilliant Idea In Publishing
  11. Giving Some Thanks Around the Globe
  12. A Neat Result About The Simplex Algorithm
  13. Another Annoying Open Problem
  14. More Quantum Chocolate Boxes
  15. Taking Passes at NP Versus L
  16. The Group Isomorphism Problem: A Possible Polymath Problem?
  17. Who’s Afraid Of Arrow’s Paradox?
  18. An Interview With Kurt Gödel
  19. Poker and Cantor’s Proof
  20. Quantum Chocolate Boxes
  21. What If Cantor’s Proof Is Wrong?
  22. Whose Complexity Is It Anyway?
  23. Empirical Humility
  24. An Annoying Open Problem
  25. The Role Of Memory In Theory
  26. What If Peano Is Inconsistent?
  27. Tweet `M’ For Murder
  28. Claiming Picard’s Math May Have Gaps
  29. Ask Bob
  30. Can Quantum Machines Do It All?
  31. 9/11 And The Web
  32. Complexity as Enabler
  33. Happy Birthday Michael Rabin
  34. Organic Separations
  35. Big Problems With Big Iron
  36. Testing Galactic Algorithms
  37. Math Is Like The Stock Market
  38. Is Jeopardy! in Mathematicians?
  39. Deolalikar’s Claim: One Year Later
  40. An Error Correcting Code From The Book
  41. Give Me A Lever
  42. Guessing, Again
  43. Logic In Action
  44. Self-Defeating Sentences
  45. Rabin’s 80th Birthday
  46. Hilbert’s 10.5th Problem
  47. Make Your Own World
  48. Time Chunks And Theory Nuggets
  49. Triple Century Post
  50. Getting On Base With P=NP
  51. And Then There Were Two
  52. Name That Graph
  53. Polls And Predictions And P=NP
  54. Random Remarks on RANDOM 2011
  55. Who’s your Doktorvater?
  56. Coloring Graphs Made Easy?
  57. Complexity on Forbidden-Minor Planets?
  58. Integer Factoring, Always Integer Factoring
  59. Innovating an Innovative Conference on Innovation
  60. Types of Papers
  61. How Powerful are Random Strings?
  62. Happy Anniversary To Turing’s Paper
  63. Finite Compactness?
  64. More On Coloring The Plane
  65. My Father, Robert James Regan
  66. Close Encounters of The Proof Kind
  67. A Possible Polymath Project?
  68. The Tang Effect and Theorems
  69. Navigating Cities and Understanding Proofs
  70. Guessing
  71. Congrats Ravi Kannan
  72. Succinct Constant Depth Arithmetic Circuits Are Weak
  73. Strange Places To Prove Theorems
  74. Could Euler Have Solved This?
  75. Searchin’
  76. Even Great Mathematicians Guess Wrong
  77. Why Is Everything Named After Gauss?
  78. I see it, but I don’t believe it
  79. I see it, but I don’t believe it
  80. Workshop: Computation As A Lens
  81. An Important Announcement
  82. Random Axioms and Gödel Incompleteness
  83. Philippe Flajolet 1948–2011
  84. Valiant’s Permanent Contributions
  85. Busses Come In Threes, Why Do Proofs Come In Two’s?
  86. Happy St. Patrick’s Day—Again Again.
  87. Levin’s Great Discoveries
  88. TeX Is Wonderful, What Is TeX?
  89. Buyers Who Must Have Two Items
  90. This Statement Does Not Refer To Itself
  91. Hecklers And Twecklers At Technical Talks
  92. Polynomials Are Easier Than Integers
  93. The Depth Of The Möbius Function
  94. Butterflies And Complexity Theories
  95. Are Mathematicians In Jeopardy?
  96. Classifying Papers On Classifying Problems
  97. Unmasking Quantum Computation
  98. Game Changing Conjectures In Mathematics
  99. Infinite Objects And Deep Proofs
  100. Gödel’s Lost Letter is Two Years Old
  101. Yogi Berra and Complexity Theory
  102. Factoring Is In BQP
  103. Is Factoring Really In BQP? Really?
  104. We Believe A Lot, But Can Prove Little
  105. One Review, Three Storms
  106. Stringology—The “Real” String Theory
  107. Proofs By Contradiction And Other Dangers
  108. Fourier Complexity of cirtemmyS Boolean Functions
  109. Predictions: Past And Future

2010 115

  1. Thanks To All
  2. Quotes, Quoting, and Quotations
  3. Unexpected Connections In Mathematics
  4. Some Mathematical Gifts
  5. What Is Big? What Is Small?
  6. Making A Heuristic Into A Theorem
  7. Jokes, Movies, And Predictions
  8. Logarithms, Tables, and Babylonians
  9. What Makes A Theorem Important?
  10. How To Stop Wikileaks?
  11. Notation And Thinking
  12. Thanksgiving Day, Pardons, and Turkeys
  13. Who Wants Parallel Computers?
  14. Is Complexity Theory On The Brink?
  15. How Ryan’s Circuit Lower Bound Works
  16. Can We Translate English To English?
  17. A Breakthrough Result
  18. What Is A Complexity Class?
  19. Equations Over Groups: A Mess
  20. The Warranty On Nisan’s Generator
  21. The Accidental Astrophysicists
  22. Galactic Algorithms
  23. Miracle Numbers Such as “56”
  24. David Hilbert Speaks
  25. Strong Codes For Weak Channels
  26. What Would You Ask Vina?
  27. Math and Theory Proof Methods: A Comparison
  28. Drug Doping and Mathematics
  29. Mathematical Intuition—What Is It?
  30. Can Group Theory Save Complexity Theory?
  31. Who Gets The Credit—Not Facebook Credits
  32. Are Quantum Impossibility Proofs Possible?
  33. My Book On P=NP Is Now Available
  34. An Update On Vinay Deolalikar’s “Proof”
  35. How To Present A Big Result
  36. Beating A Forty Year Old Result: Hamilton Cycles
  37. Promise Problems And TWOPATHS
  38. Old Ideas And Lower Bounds On SAT
  39. Projectors Not Projections
  40. Lower Bounds and Progressive Algorithms
  41. Quantum Algorithms A Different View—Again
  42. Einstein And The P≠NP Question
  43. Projections Can Be Tricky
  44. Proofs, Proofs, Who Needs Proofs?
  45. The P≠NP “Proof” Is One Week Old
  46. Fatal Flaws in Deolalikar’s Proof?
  47. Deolalikar Responds To Issues About His P≠NP Proof
  48. Deolalikar Responds To Issues About His P≠NP Proof
  49. Update on Deolalikar’s Proof that P≠NP
  50. Issues In The Proof That P≠NP
  51. A Proof That P Is Not Equal To NP?
  52. Hilbert’s Tenth Over The Rationals
  53. Quantum Algorithms A Different View
  54. Paranoia And Selling A Laptop
  55. Hedy Lamarr the Inventor
  56. A New Million Dollar Prize?
  57. An Amazing Paper
  58. Making An Algorithm An Algorithm—BBP
  59. Proving A Proof Is A Proof
  60. Playing Head-To-Head Texas hold’em
  61. Can Amateurs Solve P=NP?
  62. Stating P=NP Without Turing Machines
  63. Cheating Tournaments
  64. Guessing the Truth
  65. The Power of Uniqueness
  66. Does Cantor’s Diagonalization Proof Cheat?
  67. A Sampler From STOC 2010
  68. An Amplification Trick and STOC 2010
  69. The Tensor Trick and Tutte’s Flow Conjectures
  70. Making Abstract Data Types Abstract
  71. Let’s Have a Meeting
  72. Sorting Out Chess Endgames
  73. The Shadow Case Model of Complexity
  74. Can We Solve Chess One Day?
  75. Breaking All the Security Rules
  76. Unique Games: A Three Act Play
  77. Playing Games and Packing Graphs
  78. Limits on The Number of Co-Authors?
  79. Natural, Natural, and Natural
  80. How Fast Can We Simulate Guessing?
  81. A Post on Post
  82. Great Proofs as Great Art
  83. Socks, Shoes, and The Axiom of Choice
  84. Can We Trust Cloud Computing?
  85. Graph Isomorphism and Graph Minors
  86. April Fool
  87. A Problem With Proving Problems Are Hard
  88. Fast Matrix Products and Other Amazing Results
  89. It’s Ada Lovelace Day
  90. Logic Meets Complexity Theory
  91. The Quarterback and the Professor
  92. Happy St. Patrick Day—Again
  93. Breaking Provably Secure Systems
  94. A Class of Graph Properties Computable in Linear Time
  95. The Nominees for Best Result are …
  96. Beating Bellman for The Knapsack Problem
  97. Is It Time To Stop Malware—Forever?
  98. Proving That Proving Is Hard
  99. Alpha, Beta, Delta, and the Nullstellensatz
  100. Cups, Peas, and Grothendieck
  101. Will My Paper Be Accepted at FOCS?
  102. Trains, Elevators, and Computer Science
  103. A 2010 Algorithm for the Knapsack Problem
  104. Climbing Mountains and Proving Theorems
  105. Happy Birthday to Gödel’s Lost Letter
  106. An Educational Extinction Event?
  107. Programming Turing Machines is Hard
  108. Definitions, Definitions, Do We Need Them?
  109. Are The Reals Really Uncountable?
  110. A Limit of First Order Logic
  111. A Course on Complexity Theory
  112. Why Do We Need Cyber-Security?
  113. My Sister: Linda Lipton-North
  114. An Approach to P=NP via Descriptive Complexity
  115. My Predictions for The New Year

2009 130

  1. Thanks and Happy New Year
  2. Mathematical Embarrassments
  3. Some of My Favorite Books
  4. The 3 Percent Solution
  5. The Descriptive Complexity of Solutions
  6. Does a Trillion-To-One Make Sense?
  7. Routing Forever on an Expander Graph
  8. Is There a Test for Consciousness?
  9. The Curious History of the Schwartz-Zippel Lemma
  10. What Are Proofs For Anyway?
  11. New Streaming Algorithms for Old Problems
  12. Nash Equilibrium for Sparse Games: Part Deux
  13. More on Mathematical Diseases
  14. Rumors and Playing Games
  15. On Mathematical Diseases
  16. The Iceberg Effect in Theory Research
  17. Highlights of FOCS Theory Day
  18. Helping Wall Street Cheat With Theory
  19. Happy Fiftieth Birthday FOCS
  20. Multi-Party Protocols and FOCS 2009
  21. Magical Results and P=NP
  22. The Surprising Power of Rational Functions
  23. The World is Digital
  24. An Approach to the P=NP Question?
  25. Surprises in Mathematics and Theory
  26. It’s All Algorithms, Algorithms and Algorithms
  27. Why Believe That P=NP Is Impossible?
  28. Theory Has Bet On P=NP
  29. Are Impossibility Proofs Possible?
  30. Would You Bet Your Life?
  31. The Permanent of Stable Matrices with Few Negative Entries
  32. Counting Cycles of a Permutation in Parallel
  33. The Orbit Problem
  34. Permanents of Matrices With Negative Coefficients?
  35. Stockmeyer’s Approximate Counting Method
  36. Streaming Models both Old and New
  37. What Will Happen When P≠NP Is Proved?
  38. On The Intersection of Finite Automata
  39. Amplifying on the PCR Amplifier
  40. The Role of Amplifiers in Science
  41. Fermat’s Little Theorem for Matrices
  42. Circuits Bounds for Turing Machine Computations
  43. The Chinese Remainder Theorem With Limits
  44. Complexity Classes Meet Particle Physics
  45. Oblivious Turing Machines and a “Crock”
  46. How To Avoid O-Abuse and Bribes
  47. Open Problems in High Dimension Geometry
  48. Graphs, Permutations, Characters, and Logspace
  49. The Next Posts
  50. A New Approach To Random Spanning Trees
  51. SAT Solvers: Is SAT Hard or Easy?
  52. Arithmetic Complexity and Symmetry
  53. NSF Workshop Summary
  54. NSF Workshop On Design Automation and Theory
  55. Linear Equations Over Composite Moduli
  56. Is P=NP an Ill Posed Problem?
  57. The Isolation Lemma and Beyond
  58. Solving Diophantine Equations the Easy Way
  59. Kolata on Funding Research
  60. The Inverse Spanning Tree Problem
  61. Adaptive sampling and timed adversaries
  62. High Dimensional Search and the NN Problem
  63. BDD’s and Factoring
  64. A Proof System Based on Ramsey Theory
  65. Computing Very Large Sums
  66. When Min-Max is Wrong
  67. The Junta Problem
  68. Moser’s Method of Bounding a Program Loop
  69. Some Highlights from STOC
  70. Papadimitriou and RCT
  71. Papadimitriou and RCT
  72. Arithmetic Hierarchy and P=NP
  73. I Hate Oracle Results
  74. Zig-Zag Zig-Zag Zig-Zag
  75. Boolean Solutions to Polynomials Modulo a Prime
  76. New Ideas On Nondeterministic Simulation
  77. Simulation of Nondeterministic Turing Machines-Again
  78. Simulation of Nondeterministic Machines
  79. Happy Mother’s Day
  80. Worst Case Complexity
  81. An Approach to Graph Isomorphism?
  82. Great Papers in Theory
  83. Brouwer’s Fixed Point Theorem is Unstable
  84. How to Solve P=NP?
  85. The Four Color Theorem
  86. Fads and the Theory of Computation
  87. Cantor’s Non-Diagonal Proof
  88. The Word Problem for Free Groups
  89. SAT is Not Too Easy
  90. An EXPSPACE Lower Bound
  91. Savitch’s Theorem
  92. Factoring Again: No Joking
  93. A New Factoring Algorithm
  94. A New Factoring Algorithm
  95. Halmos, Non-Standard Analysis and Names
  96. Erdös and the Quantum Method
  97. Who’s Afraid of Natural Proofs?
  98. Bellman, Dynamic Programming, and Edit Distance
  99. The Unbounded Power Of Randomness
  100. Minsky Did Theory
  101. Happy St Patrick’s Day and Sum of Squares
  102. Cook’s Class Contains Pi
  103. Cook’s Class Contains Pi
  104. Liskov Wins The Turing Award
  105. Liskov Wins The Turing Award
  106. Factoring Could be Easy
  107. Finite State Automata, Binary Decision Diagrams and Presburger Arithmetic
  108. Ron Graham Gives a Talk
  109. Barrington Gets Simple
  110. Rabin Flips a Coin
  111. Where are the Movies on P=NP?
  112. Guessing Simulations
  113. Problems not Algorithms
  114. The Real Conjecture of Hartmanis
  115. Obama and P=NP
  116. Factoring and Factorials
  117. A Stimulus Package for P=NP
  118. Computational Thinking and The Stimulus Package
  119. We All Guessed Wrong
  120. Insider Baseball and P=NP
  121. Does the Distributive Law Work?
  122. The Knapsack Problem is Not Too Easy
  123. Proofs and Elevator Rides
  124. Algorithms: Tiny Yet Powerful
  125. Fast Exponential Algorithms
  126. “O” Abuse
  127. More “O” Abuse
  128. A Nightmare about SAT
  129. NP too big or P too small?
  130. Bait and Switch: Why Are Lower Bounds so Hard?